Cod sursa(job #2316058)

Utilizator mihail2Dan UVT mihail2 Data 10 ianuarie 2019 23:26:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>


struct nod {
    long data;
    nod *urm;
};

char v[400005];
long n, nc, m, i;
nod *l[400005];


void add(nod *&p, long x) {
    nod *c;
    c = new nod;
    c->data = x;
    c->urm = 0;
    if (!p)
        p = c;
    else {
        c->urm = p;
        p = c;
    }
}


void dfs(long i) {
    nod *c;

    v[i] = 1;
    c = l[i];

    while (c != NULL) {
        if (v[c->data] == 0)
            dfs(c->data);
        c = c->urm;
    }

}


int main() {
    std::ifstream cin("dfs.in");
    std::ofstream cout("dfs.out");

    long x, y;
    cin >> n >> m;
    for (i = 1; i <= m; i++) {
        cin >> x >> y;
        add(l[x], y);
        add(l[y], x);
    }

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

    cout << nc;
    cout.close();
    return 0;
}