大致题意#

求结点数为 $n$ 并且任意取三结点均为连通图但不是环的无向图的最大边数 $m$，并输出任意一种可能。

思路/解析#

这是一道抽屉原理的题。我们只需要 $2$ 个抽屉就可以保证任意取 $3$ 个点不可能形成环，因为至少有一个抽屉存在 $2$ 个及以上的点。但是如果将抽屉的数量增加到 $3$ 个，那么就有可能存在没个抽屉 $1$ 个点的情况，这样就有可能存在环。因此，我们只需要 $2$ 个抽屉，并保证同一抽屉内的点不连边，不同抽屉的点连边即可。

对于答案数量，我们只需要平均分成两组就好了。注意当 $n$ 为奇数时需要加 $1$。

代码#

1
#include<bits/stdc++.h>
2
using namespace std;
3
int n,m,i,j;
4
int main(){
5
 cin>>n;
6
 if(n%2==1)m=(n/2)*(n/2+1);
7
 else m=(n/2)*(n/2);
8
 cout<<m<<'\n';
9
 for(i=1;i<=n/2;i++)
10
  for(j=n/2+1;j<=n;j++)
11
   cout<<i<<' '<<j<<'\n';
12
}