?? 030300741equiv.cpp
字號:
//這道題目肯定很多人都一樣,課本上原原本本照抄就可以!!
#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++)//數(shù)據(jù)輸入
{
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;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -