Cod sursa(job #2842687)

Utilizator ptudortudor P ptudor Data 1 februarie 2022 12:34:45
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
ifstream in("ctc.in");
ofstream out("ctc.out");
#endif

///this find the strongly connected components of directed
///graph g. It assumes the nodes in g are 1-indexed.
///the return value is a vector containing vectors representing
///the strongly connected components, by nodes.

vector<int> vis,tout;
int nr;
vector<int> List;
void dfs(int node, const vector<vector<int>> &g) {
    vis[node] = 1;
    for (auto k : g[node]) {
        if (vis[k] == 0) {
            vis[k] = 1;
            dfs(k ,g);
        }
    }
    tout[node] = ++nr;
    List.push_back(node);
}
vector<int> component;
void dfs2(int node, const vector<vector<int>> &g) {
    vis[node] = 1;
    component.push_back(node);
    for (auto k : g[node]) {
        if (vis[k] == 0) {
            vis[k] = 1;
            dfs2(k ,g);
        }
    }
}

vector<vector<int>> scc(const vector<vector<int>> &g) {
    int n = (int)g.size() - 1;
    vector<vector<int>> revG(n + 1);
    for (int i = 1; i <= n; i++) {
        for (auto k : g[i]) {
            revG[k].push_back(i);
        }
    }

    nr = 0;
    tout = vis = vector<int>(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        if (vis[i] == 0) {
            dfs(1, g);
        }
    }

    vis = vector<int>(n + 1, 0);
    nr = 0;
    vector<vector<int>> res;
    for (int i = List.size() - 1; i >= 0; i--) {
        int node = List[i];
        if (vis[node] == 0) {
            nr++;
            component.clear();
            dfs2(node, revG);
            res.push_back(component);
        }
    }
    return res;
}
int main() {
    int n,m;
    in >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i <= m; i++) {
        int u,v;
        in >> u >> v;
        g[u].push_back(v);
    }
    vector<vector<int>> sol = scc(g);

    out << sol.size() << "\n";
    for (auto k : sol) {
        for (auto node : k) {
            out << node << " ";
        }
        out << "\n";
    }
    return 0;
}