Cod sursa(job #457034)

Utilizator S7012MYPetru Trimbitas S7012MY Data 17 mai 2010 20:43:22
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>

int m,n,mar[200000];

struct nod {
    int x;
    nod *urm;
};
nod v[200001];

void adaugare(nod *a, int b) {
    nod *p;
    p=new nod;
    p->x=b;
    p->urm=a;
    a=p;
}

void dfs(int d) {
    nod *p;
    mar[d]=1;
    for(*p=v[d];p!=NULL;p=p->urm)
        if(!mar[(int)p->urm])
            dfs((int)p->urm);
}

int main()
{
    int i,x,y,cont=0;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1; i<=m; i++) {
        scanf("%d %d", &x, &y);
        adaugare(&v[x],y);
        adaugare(&v[y],x);
    }
    for(i=1; i<=n; i++)
        if(!mar[i]) {
            cont++;
            dfs(i);
        }
    printf("%d\n",cont);
    return 0;
}