Pagini recente » Cod sursa (job #1096041) | Cod sursa (job #2088169) | Cod sursa (job #2978549) | Cod sursa (job #1666335) | Cod sursa (job #1757763)
#include <stdio.h>
int rg[100009],fr[100009],n,m,i,x,y,r,p[100009];
int find(int x)
{
r=x;
while (r!=p[r])
r=p[r];
while (x!=p[x])
{
x=p[x];
p[x]=r;
}
return r;
}
void uneste(int x,int y)
{
x=find(x);
y=find(y);
if (x!=y)
{
if (rg[x]>rg[y])
{
p[y]=x;
rg[x]+=rg[y];
} else
{
p[x]=y;
rg[y]+=rg[x];
}
}
}
int main(int argc, char const *argv[])
{
FILE * in =fopen("dfs.in","r");
fscanf(in,"%d%d",&n,&m);
for (i=1;i<=n;++i)
p[i]=i,rg[i]=1;
while (m--)
{
fscanf(in,"%d%d",&x,&y);
uneste(x,y);
}
for (i=1;i<=n;++i)
fr[p[i]]++;
m=0;
for (i=1;i<=n;++i)
if (fr[i]!=0)
m++;
fprintf(fopen("dfs.out","w"),"%d",m);
return 0;
}