Cod sursa(job #457042)

Utilizator S7012MYPetru Trimbitas S7012MY Data 17 mai 2010 21:04:15
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>

int m,n,mar[200000];

typedef struct nod {
    int x;
    nod *urm;
} *pnod;
pnod 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[(p->urm)->x])
            dfs((p->urm)->x);
}

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;
}