Cod sursa(job #303929)

Utilizator tibiletsKoos Tiberiu Iosif tibilets Data 10 aprilie 2009 15:30:10
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.45 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);}
for(x=1;x<=N;++x)
 if(!s[x])
 {++k;
  df(x);
 }
g<<k;
return 0;
}