Mai intai trebuie sa te autentifici.
Cod sursa(job #160115)
| Utilizator | Data | 14 martie 2008 19:05:31 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.59 kb |
#include <stdio.h>
FILE *f=fopen("dfs.in","r"),*g=fopen("dfs.out","w");
int n,m,viz[100001],nr;
typedef struct nod
{
int x;
nod *a;
} *pNod;
pNod v[100001];
void add(pNod &dest,int val)
{
pNod p;
p=new nod;
p->x=val;
p->a=dest;
dest=p;
}
void dfs(int nod)
{
pNod p;
viz[nod]=1;
for (p=v[nod];p!=NULL;p=p->a)
if(!viz[p->x]) dfs(p->x);
}
int main()
{
int i,x,y;
fscanf(f,"%d %d",&n,&m);
for (i=1;i<=m;i++)
{
fscanf(f,"%d %d",&x,&y);
add(v[x],y);
add(v[y],x);
}
for(i=1;i<=n;i++)
if(!viz[i]) {nr++;dfs(i);}
fprintf(g,"%d",nr);
return 0;
}
