Pagini recente » Cod sursa (job #2508397) | Cod sursa (job #297559) | Cod sursa (job #2341795) | Cod sursa (job #1813011) | Cod sursa (job #396686)
Cod sursa(job #396686)
#include<stdio.h>
#include<stdlib.h>
#define NMAX 100024
//back to stone-age
int *A[NMAX];
int G[NMAX];
int viz[NMAX];
void DFS( int nod )
{
int i=1,a1;
for( i=1; i<=A[nod][0]; ++i )
{
a1=A[nod][i];
if( !viz[a1] )
{
viz[a1]=1;
DFS(a1);
}
}
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
int N,M;
scanf("%d%d",&N,&M);
int i;
int a1,a2;
for(i=1; i<=N; ++i)
{
A[i]=(int *) realloc( A[i], sizeof(int) );
A[i][0]=0;
}
for(i=1; i<=M; ++i)
{
scanf("%d%d",&a1,&a2);
++A[a1][0];
A[a1]=(int *) realloc( A[a1], (A[a1][0]+1)*sizeof(int) );
A[a1][ A[a1][0] ]=a2;
++A[a2][0];
A[a2]=(int *) realloc( A[a2], (A[a2][0]+1)*sizeof(int) );
A[a2][ A[a2][0] ]=a1;
}
int ans=0;
for( i=1; i<=N; ++i )
{
if( !viz[i] )
{
viz[i]=1;
++ans;
DFS(i);
}
}
printf("%d\n",ans);
return 0;
}