Cod sursa(job #303930)
| Utilizator | 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;
}
