Cod sursa(job #556464)

Utilizator UpL1nKPaunescu Sorin UpL1nK Data 16 martie 2011 09:56:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>

using namespace std;

struct nod {

    int inf;
    nod *next;

} *G[100001];

int n, m;
int used[100001];
int nrC;

void adauga(int x, int inf) {

    nod *aux = new nod;
    aux->inf = inf;
    aux->next = G[x];
    G[x] = aux;

}

void afiseaza(int x) {

    printf("Nodul %d: ", x);
    for (nod *p = G[x]; p; p = p->next)
        printf("%d ", p->inf);
    printf("\n");

}

void dfs(int x) {

    used[x] = 1;
    for (nod *p = G[x]; p; p = p->next)
        if (!used[p->inf])
            dfs(p->inf);

}

int main() {

    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    scanf("%d %d", &n, &m);

    int x, y;

    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
        adauga(x, y);
        adauga(y, x);
    }

    for (int i = 1; i <= n; i++)
        if (!used[i]) {
            dfs(i);
            nrC++;
        }

    printf("%d", nrC);

    return 0;
}