Cod sursa(job #699075)
| Utilizator | Data | 29 februarie 2012 17:25:06 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 15 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.49 kb |
#include<stdio.h>
int a[100010],max=0;
void search(int x,int y)
{
int i;
for(i=1;i<=max;i++)
if(a[i]==x)
a[i]=y;
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
int n,k,i,no=0,x,y;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
{a[i]=i;}
for(i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
if(x>max)
max=x;
if(y>max)
max=y;
if(x<y)
search(a[y],x);
else
search(a[x],y);
}
for(i=1;i<=n;i++)
if(a[i]==i)
no++;
printf("%d",no);
return 0;
}
