Pagini recente » Cod sursa (job #277927) | Cod sursa (job #2468357) | Cod sursa (job #2720868) | Cod sursa (job #1281782) | Cod sursa (job #372575)
Cod sursa(job #372575)
#include<fstream>
using namespace std;
int n,m,t[100004],nrc,h[100004];
int rad(int x)
{
int y,tmp;
y=x;
while(t[x])
x=t[x];
while(y!=x)
{
tmp=y;
y=t[y];
t[tmp]=x;
}
return x;
}
void reuniune(int x,int y)
{
int rx=rad(x);
int ry=rad(y);
if(rx!=ry)
{
nrc--;
if(h[rx]>h[ry])
t[ry]=rx;
else
{
if(h[rx]<h[ry])
t[rx]=ry;
else
t[rx]=ry,h[ry]++;
}
}
}
int main()
{
ifstream fin("dfs.in");
fin>>n>>m;
nrc=n;
for( ; m ;m--)
{
int i,j;
fin>>i>>j;
reuniune(i,j);
}
ofstream fout("dfs.out");
fout<<nrc;
return 0;
}