Pagini recente » Cod sursa (job #2863577) | Cod sursa (job #13016) | Cod sursa (job #538009) | Cod sursa (job #856391) | Cod sursa (job #372580)
Cod sursa(job #372580)
using namespace std;
#include<fstream>
int n,m,nrc,t[100000],h[100000];
int radacina(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=radacina(x);
int ry=radacina(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()
{
int i,x,y;
ifstream fin("dfs.in");
fin>>n>>m;
nrc=n;
for(i=1;i<=m;i++)
{
fin>>x>>y;
reuniune(x,y);
}
fin.close();
ofstream fout("dfs.out");
fout<<nrc;
fout.close();
return 0;
}