Cod sursa(job #215682)

Utilizator StigmaSimina Pitur Stigma Data 20 octombrie 2008 12:52:49
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <iostream.h>
#include <fstream.h>

ifstream fin("dfs.in");
ofstream fout("dfs.out");


struct nod{long info; nod *urm;};

char v[100005];
long n,nc,m,i;
nod *l[100005];


void add(nod *&p, long x)
{nod *c;
 c=new nod;
 c->info=x;
 c->urm=0;
 if (!p) p=c;
 else
  {c->urm=p;
   p=c;
  }
}



void dfs(int i)
{long j;
nod *c;
v[i]=1;
c=l[i];

while (c)
{dfs(c->info);
 c=c->urm;
}

}

int main()
{long x,y;
 fin>>n>>m;
 for (i=1;i<=m;i++)
 {fin>>x>>y;
  add(l[x],y);
  add(l[y],x);
 }

for (i=1;i<=n;i++)
if (v[i]==0) {nc++; dfs(i);}

fout<<nc;
fout.close();
return 0;
}