Pagini recente » Cod sursa (job #360605) | Cod sursa (job #3143522) | Cod sursa (job #2090572) | Cod sursa (job #3266523) | Cod sursa (job #3278299)
#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);
low[node] = min(low[node], low[son]);
} else if(onStack[son]) {
low[node] = min(low[node], low[son]);
}
}
if(id[node] == low[node]) {
scc.push_back({});
while(st.top() != node) {
scc.back().push_back(st.top());
onStack[st.top()] = false;
st.pop();
}
scc.back().push_back(st.top());
onStack[st.top()] = false;
st.pop();
}
};
for(int i = 1; i <= n; i++) {
if(!id[i]) {
dfs(i);
}
}
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;
}