Cod sursa(job #303930)

Utilizator tibiletsKoos Tiberiu Iosif tibilets Data 10 aprilie 2009 15:31:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.47 kb
#include<fstream.h>
int N,M,x,y,k;
short s[100001];
struct nod
{int v;
 nod *adr;}*L[100001];
void push(int n,int v)
{nod *p=new nod;
 p->v=v;
 p->adr=L[n];
 L[n]=p;}
void df(int x)
{s[x]=1;
 nod *p=L[x];
 while(p)
 {if(!s[p->v])
   df(p->v);
  p=p->adr;
 }
}
int main()
{ifstream f("dfs.in");
ofstream g("dfs.out");
f>>N>>M;
for(;M;--M)
{f>>x>>y;
 push(x,y);
 push(y,x);
}
for(x=1;x<=N;++x)
 if(!s[x])
 {++k;
  df(x);
 }
g<<k;
return 0;
}