Cod sursa(job #2199625)

Utilizator MateiTrandafirMatei Trandafir MateiTrandafir Data 28 aprilie 2018 15:40:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>

#define N 100001
#define M 200001

int n, m, nr, nodes[2 * M], next[2 * M], list[M];
bool vis[N];

// Node 'to' can be reached from node 'from'
inline void add(int from, int to) {
    ++nr;
    nodes[nr] = to;
    next[nr] = list[from];
    list[from] = nr;
}

inline bool dfs(int start) {
    if (vis[start]) return false;
    vis[start] = true;
    int p = list[start];
    while (p != 0) {
        dfs(nodes[p]);
        p = next[p];
    }
    return true;
}

int main() {
    std::ifstream in("dfs.in");
    std::ofstream out("dfs.out");
    in >> n >> m;
    int x, y;
    for (int i = 0; i < m; ++i) {
        in >> x >> y;
        add(x, y);
        add(y, x);
    }
    int r = 0;
    for (int i = 1; i <= n; ++i) if (dfs(i)) ++r;
    out << r;
    return 0;
}