Pagini recente » Cod sursa (job #2274030) | preONI 2008 - Clasament Runda 1, Clasele 11-12 | Cod sursa (job #198588) | Cod sursa (job #817632) | Cod sursa (job #326366)
Cod sursa(job #326366)
#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;
}