Cod sursa(job #147481)

Utilizator p1ccolinoAlexandru Vlad p1ccolino Data 2 martie 2008 22:56:42
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<fstream.h>
long n,viz[100001],nrc;
long m,st[100001];
struct nod{long x; nod*urm;} *l[100001];

void dfs(int v)
{nrc++;
 long vf=1; viz[v]=nrc;
 while (vf)
 { nod*p=l[st[vf]];
 while (p&&viz[p->x]) p=p->urm;
 if(p){vf++; st[vf]=p->x;
 viz[p->x]=nrc;}
 else vf--;}}

int main()
{long i,v1,v2;
ifstream f("dfs.in");
f>>n>>m;
for(i=1;i<m+1;i++)										
{f>>v1>>v2;
nod *p=new nod;p->x=v1;p->urm=l[v2];
l[v2]=p;
nod *q=new nod;q->x=v2;q->urm=l[v1];
l[v1]=q;
}						
f.close();
for(i=1;i<n+1;i++)
if(viz[i]==0) dfs(i);
ofstream g("dfs.out");
g<<nrc<<"\n";
g.close();
return 0;}