Pagini recente » Cod sursa (job #167129) | Cod sursa (job #1646589) | Cod sursa (job #919189) | Cod sursa (job #367019) | Cod sursa (job #3203030)
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
inline void setup_io() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
}
template <typename T>
using vec = vector<T>;
class Graph {
vec<vec<int>> adj, scc;
vec<bool> processed;
vec<int> tin;
stack<int> st;
int N, timer;
int dfs(int u) {
int low = tin[u] = ++timer;
st.push(u);
for (int v : adj[u])
if (!processed[v])
low = min(low, tin[v] ?: dfs(v));
if (low == tin[u]) {
scc.emplace_back();
for (; st.top() != u; st.pop()) {
scc.back().push_back(st.top());
processed[st.top()] = true;
}
processed[u] = true;
scc.back().push_back(u);
st.pop();
}
return low;
}
public:
Graph(int N) : N(N), adj(N), tin(N), processed(N) {}
void add_edge(int u, int v) {
adj[u].push_back(v);
}
vec<vec<int>> strongly_connected_components() {
fill(tin.begin(), tin.end(), 0);
fill(processed.begin(), processed.end(), false);
scc.clear();
timer = 0;
for (int u = 0; u < N; ++u)
if (!tin[u]) dfs(u);
// strongly connected components in topological order
reverse(scc.begin(), scc.end());
return scc;
}
};
int main() {
setup_io();
int N, M, u, v;
cin >> N >> M;
Graph graph(N);
for (int i = 0; i < M; ++i) {
cin >> u >> v;
graph.add_edge(u - 1, v - 1);
}
auto scc = graph.strongly_connected_components();
cout << scc.size() << '\n';
for (const vec<int> &comp : scc) {
for (int u : comp) cout << u + 1 << ' ';
cout << '\n';
}
return 0;
}