Cod sursa(job #904941)

Utilizator stelutaSfiriac Bianca steluta Data 5 martie 2013 07:52:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<cstdio>
using namespace std;

typedef struct Nod {
    int nod;
    Nod *urm;
} NOD;

NOD *p, *v[100005];
int n, m, i, a, b, comp, viz[100005];

void dfs (int x) {
    NOD *q;
    int t;

    viz[x]=1;
    q=v[x];

    while (q->urm != NULL) {
        t=q->nod;
        if (viz[t]==0) dfs(t);
        q=q->urm;
    }
}

int main () {
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    scanf("%d %d", &n, &m);

    for (i=1; i<=n; ++i) {
        v[i]=new NOD;
        v[i]->nod=100005;
        v[i]->urm=NULL;
    }

    for (i=1; i<=m; ++i) {
        scanf("%d %d", &a, &b);

        p=new NOD;
        p->nod=a;
        p->urm=v[b];
        v[b]=p;

        p=new NOD;
        p->nod=b;
        p->urm=v[a];
        v[a]=p;
    }

    comp=0;
    for (i=1; i<=n; ++i) {
        if (viz[i]==0) {
            ++comp;
            dfs(i);
        }
    }

    printf("%d\n", comp);

    return 0;
}