Cod sursa(job #662165)
#include<stdio.h>
#define MAX 100010
using namespace std;
typedef struct nod { int info;
nod *next;} pnod;
pnod *G[MAX];
int viz[MAX];
int n,m;
void DFs(int nod1)
{
viz[nod1]=1;
pnod *a=new nod;
a=G[nod1];
while (a)
{if (viz[a->info]==0) DFs(a->info);
a=a->next;
}
}
int main()
{ pnod*a;
int i,x,y;
freopen("dfs.in", "r",stdin);
freopen("dfs.out", "w",stdout);
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
a=new nod;
a->next=G[x];
a->info=y;
G[x]=a;
a=new nod;
a->next=G[y];
a->info=x;
G[y]=a;
}
int conex=0;
for (i=1;i<=n;i++)
if (viz[i]==0) {
conex++;
DFs(i);}
printf("componente conexe %d\n",conex);
return 0;
}