CF41E 3-cycles 题解

大致题意

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

思路/解析

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

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

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j;
int main(){
	cin>>n;
	if(n%2==1)m=(n/2)*(n/2+1);
	else m=(n/2)*(n/2);
	cout<<m<<'\n';
	for(i=1;i<=n/2;i++)
		for(j=n/2+1;j<=n;j++)
			cout<<i<<' '<<j<<'\n';
}