Cod sursa(job #302697)

Utilizator TyberFMI Dogan Adrian Ioan Lucian Tyber Data 9 aprilie 2009 10:25:58
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<stdio.h>
typedef struct tnod{int x;
	    tnod*urm;} *pnod;
pnod v[200000];
int n,m,s[200000],c;
void add(pnod&,int);
void df(int);
int main(){
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){int x,y;
		      scanf("%d %d",&x,&y);
		      add(v[x],y);
		      add(v[y],x);}
for(int i=1;i<=n;i++)if(s[i]==0){c++;
				 df(i);}
printf("%d\n",c);
return 0;}
void add(pnod &d,int t){pnod *p;
			p=new pnod;
			p->x=t;
			p->urm=d;
			d=p;}
void df(int t){pnod *p;
	       s[t]=1;
	       for(p=v[t];p!=NULL;p=p->urm)if(s[p->x]==0)df(p->x);}