Cod sursa(job #1646540)

Utilizator AlexxanderXPrisacariu Alexandru AlexxanderX Data 10 martie 2016 16:33:23
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>

struct nod {
    int x;
    nod* p;
};

nod* a[100000];
bool b[100000];

void add(nod *&dest, int x) {
    nod* p = new nod;
    p->x = x;
    p->p = dest;

    //std::cout << "p->x = " << x << " && p->p = " << dest << " => dest = " << p << "\n";

    dest = p;
}

void DFS(int nodd) {
    b[nodd] = 1;
    for (nod* p=a[nodd]; p != NULL; p = p->p) {
        if (!b[p->x]) DFS(p->x);
    }
}

int main() {
    std::ifstream f("dfs.in");
    int n, m;
    f >> n >> m;

    int x, y;
    for (int i=0; i<m; ++i) {
        f >> x >> y;
        //std::cout << x << " " << y << "\n";
        add(a[x], y);
        add(a[y], x);
    }

    // for (int i=1; i<=n; ++i) {
    //     if (a[i] != NULL) std::cout << i << ":" << a[i]->x << ", " << a[i]->p << "\n";
    //     else std::cout << i << " NULL\n";
    // }

    int c = 0;
    for (int i=1; i<=n; ++i) {
        if (!b[i]) {
            ++c;
            DFS(i);
        }
    }

    std::cout << c << "\n";
}