好等价类划分741equiv.cpp

来自「设计一个算法」· C++ 代码 · 共 85 行

//这道题目肯定很多人都一样,课本上原原本本照抄就可以!!
#include <iostream.h>
#include <fstream.h>

class UnionFind{
public:
	UnionFind(int n);
	~UnionFind(){delete [] parent;delete [] root;}
	int Find(int e);
	void Union(int i,int j);
	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()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	int n,m,A,B,a,b;
	in>>n>>m;
	UnionFind  unio(n);
	for(int i=1;i<=m;i++)//数据输入
	{
		in>>a>>b;
		A=unio.Find(a);
		B=unio.Find(b);
		if(A!=B)
			unio.Union(A,B);
	}
	int k=0;
	for(i=1;i<=n;i++)
	{
		if(unio.root[i]==true)
			k++;
	}
	out<<k<<endl;
}