Pagini recente » Cod sursa (job #1229698) | Cod sursa (job #281719) | Cod sursa (job #1602551) | Cod sursa (job #2404331) | Cod sursa (job #2053570)
#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';
}
}