?? 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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -