030300817equiv.cpp

这个源码是关于等价类划分的问题

#include<iostream.h>
#include<fstream.h>
class UFind
{
public:
	UFind(int n);
	~UFind(){delete[]parent;delete[]root;}
	int Find(int e);
	void Union(int i,int j);
	int getcount(){return count;}
private:
	int *parent;
	bool *root;
	int count;
};
UFind::UFind(int n)
{
	count=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 UFind::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 UFind::Union(int i,int j)
{
	if(i!=j)
	{
		if(parent[i]<parent[j])
		{
			parent[j]+=parent[i];
			root[i]=false;
			parent[i]=j;
			count--;
		}
		else
		{
			parent[i]+=parent[j];
			root[j]=false;
			parent[j]=i;
			count--;
		}
	}
}
main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	int a,b,n,m,i=0;
	in>>n>>m;
	UFind equal(n);
	for(;i<m;i++)
	{
		in>>a>>b;
		equal.Union(equal.Find(a),equal.Find(b));
	}
	out<<equal.getcount();
	return 0;
}