Pagini recente » Cod sursa (job #2769584) | Cod sursa (job #751299) | Cod sursa (job #410663) | Cod sursa (job #215471) | Cod sursa (job #326365)
Cod sursa(job #326365)
#include <stdio.h>
#include <stdlib.h>
int n,m,*a[100001],i,comp,x,y,;
char viz[100001];
void dfs(int x)
{
viz[x]=1;
for(i=1; i<=a[x][0]; i++)
if(!viz[a[x][i]]) dfs(a[x][i]);
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d %d",&n,&m);
for(i=1; i<=n; i++)
{
a[i]=(int *)realloc(a[i],sizeof(int));
a[i][0]=0;
}
for(i=0; i<m; i++)
{
scanf("%d %d",&x,&y);
a[x][0]++;
a[x]=(int *)realloc(a[x],(a[x][0]+1)*sizeof(int));
a[x][a[x][0]]=y;
a[y][0]++;
a[y]=(int *)realloc(a[y],(a[y][0]+1)*sizeof(int));
a[y][a[y][0]]=x;
}
for(i=1; i<=n; i++)
if(!viz[i])
{
comp++;
dfs(i);
}
printf("%d",comp);
return 0;
}