Cod sursa(job #160115)

Utilizator Ionutz_LalaLala Marius Ionut Ionutz_Lala Data 14 martie 2008 19:05:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <stdio.h>
FILE *f=fopen("dfs.in","r"),*g=fopen("dfs.out","w");
int n,m,viz[100001],nr;
typedef struct nod
{
 int x;
 nod *a;
} *pNod;
pNod v[100001];
void add(pNod &dest,int val)
{
 pNod p;
 p=new nod;
 p->x=val;
 p->a=dest;
 dest=p;
}
void dfs(int nod)
{
 pNod p;
 viz[nod]=1;
 for (p=v[nod];p!=NULL;p=p->a)
   if(!viz[p->x]) dfs(p->x);
}
int main()
{
 int i,x,y;
 fscanf(f,"%d %d",&n,&m);
 for (i=1;i<=m;i++)
 {
   fscanf(f,"%d %d",&x,&y);
   add(v[x],y);
   add(v[y],x);
 }
 for(i=1;i<=n;i++)
   if(!viz[i]) {nr++;dfs(i);}
 fprintf(g,"%d",nr);
 return 0;
}