Cod sursa(job #486712)

Utilizator ClasianMunteanu Petre Clasian Data 22 septembrie 2010 17:05:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<cstdio>
#define inf 100001
using namespace std;
struct nod { int info;
			 nod*lg;
		   }*vf[inf],*r;
int use[inf],n;
void DF(int i)
{ use[i]=1;
	for(nod *p=vf[i];p;p=p->lg)if(!use[p->info])DF(p->info);
}
int main()
{ freopen("dfs.in","r",stdin);
  freopen("dfs.out","w",stdout);
  int m,i,a,b,nr=0;
  scanf("%d%d",&n,&m);
  for(i=1;i<=m;i++) { scanf("%d%d",&a,&b);
					  r=new nod;
					  r->info=b;
					  r->lg=vf[a];
					  vf[a]=r;
					  r=new nod;
					  r->info=a;
					  r->lg=vf[b];
					  vf[b]=r;
					}
  for(i=1;i<=n;i++)if(!use[i]) { DF(i);
								 nr++;
							   }
  printf("%d",nr);
  return 0;
}