[开发测试]codeforces CF1559D1.Mocha and Diana (Easy Version)

题意：
Mocha和Diana各有一个无向图，他们的无向图都是森林，森林由一个或者多个树构成，所以森林里一定不存在环。要求向Mocha和Diana的森林中同时加入某条边使得他们的图依旧没有环，最多可以加入多少条这样的边。
思路：
首先对于一棵有m个节点的树来说，这棵树一定有m-1条边，并且每两个点之间都有一条路径，而且树中的任意节点父亲节点个数不会超过一个。为什么树中一定没有环呢，假设树中有环x->y->x，这个环在无向图中其实可以看为x->y的路径有两条甚至以上，那么y这个节点就有两个甚至以上的父亲节点了，和树的定义不符合，所以树中一定是无环的。又因为树种的任意两个节点之间一定有一条路径，那么你在树中添加一条边一定会构成一个环，这里就是题目解决问题的关键了，也就是说添加边不能在同一个树中添加，可以在森林中的不同树之间添加一条边。可能又会有个问题，不同树之间添加一条边不会构成环吗，不同树一开始没有相连的边，那么从一棵树的任意节点到另一棵树的任意节点必须通过这条新添加的边，并且没办法从另一条路径回到原来的点，所以一定是没有环的。
所以这里引出了解决题目的关键，在森林中不同的树之间连边。使用并查集的解决方案，森林中每棵树一个集合，然后O(n^2)遍历所有边，看看边的两个端点是否在同一个集合中，不在则添加一条边，在则无法添加。又因为是向两个森林中同时添加某条边，所以要求两个森林中这条边的两个端点都不在同一个集合中才可以添加。这种方法一定不会少了一条边，因为对每条边都进行了判断，只要两条边属于不同集合那就添加这条边，也一定不会多出来一条边，因为都是按照符合的不会构成环的情况下添加的边。
代码思路就是O(n^2)遍历所有边，然后判断这条边在两个森林中是否都属于两个不同的集合，如果都属于不同的集合那么就方案数+1，记录这条边。
代码：

#include<bits/stdc++.h>
using namespace std;
int fa1[1005],fa2[1005];//分别为Mocha和Diana的并查集
int n,m,k;//节点总数n，Mocha一开始边的数目m，Diana一开始的边数目k
int ans=0;//方案总数
struct node
{
	int x,y;
}que[1005];//答案边
void init()//初始化并查集数组
{
	for(int i=1;i<=n;i++)
	fa1[i]=i,fa2[i]=i;

}
int get1(int x)//在Mocha的森林中返回x节点属于的集合编号
{
	if(fa1[x]==x)
	return x;
	return fa1[x]=get1(fa1[x]);
}
int get2(int x)//在Diana的森林中范围x节点属于的集合编号
{
	if(fa2[x]==x)
	return x;
	return fa2[x]=get2(fa2[x]);
}
int main()
{
	
	scanf("%d%d%d",&n,&m,&k);
	init();
	for(int i=1;i<=m;i++)//构造Mocha的并查集
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int fx=get1(x);
		int fy=get1(y);
		if(fx!=fy)
		fa1[fx]=fy;
	}	
	for(int i=1;i<=k;i++)//构造Diana的并查集
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int fx=get2(x);
		int fy=get2(y);
		if(fx!=fy)
		fa2[fx]=fy;
	}
	for(int i=1;i<=n;i++)//N^2判断每条边是否在两个人的森林中都属于不同的集合
	for(int j=1;j<=n;j++)
	{
		int x=get1(i);//i节点在Mocha的森林中属于的集合编号
		int y=get1(j);//j节点在Mocha的森林中属于的集合编号
		int x2=get2(i);//i节点在Diana的森林中属于的集合编号
		int y2=get2(j);//j节点在Diana的森林中属于的集合编号
		if(x!=y&&x2!=y2)//在两个人的森林中都属于不同的集合
		{
			ans++;//方案数+1
			que[ans].x=i;
			que[ans].y=j;//记录边情况
			fa1[x]=y;//在Mocha的树中将(i,j)这条边连接的两个集合链接起来
			fa2[x2]=y2;//在Diana的树中将(i,j)这条边连接的两个集合链接起来
		}
	}
	//输出答案
	cout<<ans<<endl;
	for(int i=1;i<=ans;i++)
	{
		cout<<que[i].x<<" "<<que[i].y<<endl;
	}
return 0;
}