Cod sursa(job #183676)

Utilizator GagosGagos Radu Vasile Gagos Data 22 aprilie 2008 14:21:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>   
typedef struct nod   
{   
    int inf;   
    nod * urm;   
} *pnod;   
pnod v[100001];   
int n,m,viz[100001],k;   
void add(pnod &p,int j)   
{   
    pnod q;   
    q=new nod;   
    q->inf=j;   
    q->urm=p;   
    p=q;   
}   
void read()   
{   
    int i,l,j;   
    scanf("%d %d",&n,&m);   
    for(l=1;l<=m;++l){   
        scanf("%d %d",&i,&j);   
        add(v[i],j);   
        add(v[j],i);   
    }   
}   
void DFS(int x)   
{   
    pnod p;   
    viz[x]=1;   
    for(p=v[x];p!=NULL;p=p->urm)   
        if(!viz[p->inf])   
            DFS(p->inf);   
}
int main()   
{   
    freopen("dfs.in","r",stdin);   
    freopen("dfs.out","w",stdout);   
    read();   
    for(int i=1;i<=n;++i)   
        if(!viz[i]){   
            DFS(i);   
            k++;   
        }   
    printf("%d\n",k);   
    fcloseall();   
    return 0;   
}