Pagini recente » Istoria paginii runda/bleble/clasament | Cod sursa (job #2435049)
#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
using namespace std;
struct Graph {
int n, timer;
vector<bool> in_stk;
vector<int> in, low, stk;
vector<vector<int>> adj, scc;
Graph(int n_) : n(n_), timer(0), in_stk(n), in(n, -1), low(n, -1), adj(n) {
stk.reserve(n);
}
void AddEdge(int u, int v) {
adj[u].emplace_back(v);
}
void Tarjan(int node) {
in[node] = low[node] = ++timer;
stk.emplace_back(node);
in_stk[node] = true;
for (int &x : adj[node]) {
if (in[x] == -1) {
Tarjan(x);
low[node] = min(low[node], low[x]);
} else if (in_stk[x]) {
low[node] = min(low[node], low[x]);
}
}
if (low[node] == in[node]) {
int x;
scc.emplace_back();
do {
x = stk.back();
stk.pop_back();
in_stk[x] = false;
scc.back().emplace_back(x);
} while (x != node);
}
}
void FindSCC() {
for (int i = 0; i < n; ++i) {
if (in[i] == -1) {
Tarjan(i);
}
}
}
vector<vector<int>> GetSCC() {
return scc;
}
};
int main() {
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m; cin >> n >> m;
Graph g(n);
while (m--) {
int u, v; cin >> u >> v;
g.AddEdge(u - 1, v - 1);
}
g.FindSCC();
auto scc = g.GetSCC();
cout << scc.size() << endl;
for (auto &comp : scc) {
for (int &x : comp) {
cout << x + 1 << ' ';
}
cout << '\n';
}
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}