Pagini recente » Cod sursa (job #2770782) | Cod sursa (job #475523) | Cod sursa (job #3272141) | Cod sursa (job #2715453) | Cod sursa (job #3278296)
#include <bits/stdc++.h>
using namespace std;
int main() {
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m;
in >> n >> m;
vector<vector<int>> g(n + 1);
for(int i = 1; i <= m; i++) {
int x, y;
in >> x >> y;
g[x].push_back(y);
}
int cnt = 0;
vector<bool> onStack(n + 1);
stack<int> st;
vector<vector<int>> scc;
vector<int> id(n + 1), low(n + 1);
function<void(int)> dfs = [&](int node) {
low[node] = id[node] = cnt++;
onStack[node] = true;
st.push(node);
for(int son : g[node]) {
if(!id[son]) {
dfs(son);
}
if(onStack[son]) {
low[node] = min(low[node], low[son]);
}
}
if(id[node] == low[node]) {
scc.push_back({});
while(1) {
int v = st.top();
scc.back().push_back(v);
st.pop();
onStack[v] = false;
if(node == v) { break; }
}
}
};
dfs(1);
out << (int)scc.size() << '\n';
for(int i = 0; i < (int)scc.size(); i++) {
for(int node : scc[i]) {
out << node << ' ';
}
out << '\n';
}
return 0;
}