conns.txt

设计用并查集来计算一个无向图的连通分支的算法。 对于给定的无向图G

#include<iostream.h>
#include<fstream.h>
ifstream fin("input.txt");
ofstream fout("output.txt");
class UnionFind{
	public:
		UnionFind(int n);
		~UnionFind(){delete[]parent;delete[]root;}
		int Find(int e);
		void Union(int i,int j);
	private:
		int *parent;
		bool*root;
};
UnionFind::UnionFind(int n)
{
	root=new bool [n+1];
	parent=new int[n+1];
	for(int e=1;e<=n;e++)
	{
		parent[e]=1;
		root[e]=true;
	}
}
int UnionFind::Find(int e)
{
	int j=e;
	while(!root[j]) j=parent[j];
	int f=e;
	while(f!=j)
	{
		int pf=parent[f];
		parent[f]=j;
		f=pf;
	}
	return j;
}
void  UnionFind::Union(int i,int j)
{
	if(parent[i]<parent[j])
	{
		parent[j]+=parent[i];
		root[i]=false;
		parent[i]=j;
	}
	else
	{
		parent[i]+=parent[j];
		root[j]=false;
		parent[j]=i;
	}
}

void main()
{
      register int i;
	
	int n,k,m,rootname1,rootname2,u,v;
	fin>>n>>k>>m;
	UnionFind wgraph(n);
	for(i=0;i<k;i++)
	{
		fin>>u>>v;
		if(u!=v)
		{
			rootname1=wgraph.Find(u);
			rootname2=wgraph.Find(v);
			if(rootname1!=rootname2)  wgraph.Union(rootname1,rootname2);
		}
	}

	for(i=0;i<m;i++)
	{
		fin>>u>>v;
		rootname1=wgraph.Find(u);
		rootname2=wgraph.Find(v);
		if(rootname1==rootname2)  fout<<"Yes"<<endl;
		else fout<<"No"<<endl;
	}
}