图论构造类问题

题意：输入n个点，要求你连接一些边，使其变为无向图，并且，在图中任选3个点，这3个点的度都不会完全相等

构造方法是

对于奇数个点，第n/2+1个点不要连线，将点集分为相等的两部分，1到n/2为一部分，n/2+2到n为一部分，从第一部分开始连线，都指向第二部分，1号点连n/2条，2号点连n/2-1条，3号点连n/2-2条………………n/2号点连1条

对于偶数个点是一样的，刚好能将点分为两个部分，两个部分的连线方法一样

（这构造太巧妙了，很容易就能看到不会有3个点的度相同）

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;int main(){    int n;    int s1,t1,s2,t2;    cin >> n;    if(n & 1)        s1 = 1 , t1 = n>>1 , s2 = (n>>1)+2 , t2 = n;    else        s1 = 1 , t1 = n>>1 , s2 = (n>>1)+1 , t2 = n;    int sum = t1 - s1 + 1;    int res = (1 + sum) * sum / 2;    cout << res << endl;    for(int i=s1; i<=t1; i++)        for(int j=s2+i-1; j<=t2; j++)            cout << i << " " << j << endl;    return 0;}