equiv.cpp

设计一个算法

#include <iostream.h>
#include <fstream.h>

class Equiv{
public:
	Equiv(int n);
	~Equiv();
	int num(int r);
	void contact(int i,int j);
	int *p;
	bool *out;
};

Equiv::Equiv(int n)
{
	out = new bool [n+1];
	p = new int [n+1];
	for(int r=1;r<n+1;r++)
	{
		p[r]=1;
		out[r]=true;
	}
}
Equiv::~Equiv()
{
	delete []p;
	delete []out;
}
int Equiv::num(int r)
{
	int j=r;
	if(!out[j]){	j=p[j]; }
	return j;
}

void Equiv::contact(int i,int j)
{
	if(p[i]<p[j])
	{
		out[i]=false;
		p[i]=j;
	}
	else
	{
		out[j]=false;
		p[j]=i;
	}
}

void main()
{
	int n,m,A,B,a,b;
	ifstream in("input.txt");
	in>>n>>m;
	Equiv  equiv1(n);
	for(int i=1;i<m+1;i++)
	{
		in>>a>>b;
		A=equiv1.num(a);
		B=equiv1.num(b);
		if(A!=B)
			equiv1.contact(A,B);
	}
	int k=0;
	for(i=1;i<n+1;i++)
	{
		if(equiv1.out[i]==true)
			k++;
	}
	ofstream out("output.txt");
	out<<k<<endl;
}