Cod sursa(job #2053570)

Utilizator retrogradLucian Bicsi retrograd Data 31 octombrie 2017 21:29:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> val, comp, stk, cont;
int timer, ncomps;

template<class Graph, class Func>
int dfs(int node, Graph& G, Func f) {
    int low = val[node] = ++timer, x; stk.push_back(node);
    for (auto vec : G[node]) if (comp[vec] < 0)
        low = min(low, val[vec] ?: dfs(vec, G, f));

    if (low == val[node]) {
        do {
            x = stk.back(); stk.pop_back();
            comp[x] = ncomps;
            cont.push_back(x);
        } while (x != node);
        f(cont); cont.clear();
        ncomps++;
    }
    return val[node] = low;
}

template<class Graph, class Func>
void SCC(Graph& G, Func f) {
    int n = G.size();
    val.assign(n, 0); comp.assign(n, -1);
    timer = ncomps = 0;
    for (int i = 0; i < n; ++i)
        if (comp[i] < 0)
            dfs(i, G, f);
}

int main() {
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");

    int n, m; cin >> n >> m;
    vector<vector<int>> G(n);
    while (m--) {
        int a, b; cin >> a >> b;
        G[a - 1].push_back(b - 1);
    }

    vector<vector<int>> comps;
    SCC(G, [&](vector<int> comp) { 
        comps.emplace_back(move(comp)); 
    });
    
    cout << comps.size() << endl;
    for (auto x : comps) {
        for (auto y : x)
            cout << y + 1 << " ";
        cout << '\n';
    }    
}