Cod sursa(job #457066)

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

int m,n,mar[100005];

typedef struct nod {
    int x;
    nod *urm;
} *pnod;
pnod v[100005];

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

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

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