Pagini recente » Cod sursa (job #3354716) | Cod sursa (job #18306) | Cod sursa (job #433791) | Cod sursa (job #3353931) | Cod sursa (job #3350355)
#include <bits/stdc++.h>
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
const int NMAX = 100005;
bool onStack[NMAX];
int low[NMAX], disc[NMAX];
std::vector<int> graph[NMAX];
std::stack<int> st;
std::vector<std::vector<int>> sccs;
void compute_sccs(int from) {
static int time = 0;
low[from] = disc[from] = ++time;
onStack[from] = true;
st.push(from);
for(int to : graph[from]) {
if(!disc[to]) {
compute_sccs(to);
low[from] = std::min(low[from], low[to]);
}
else if(onStack[to]) {
low[from] = std::min(low[from], low[to]);
}
}
if(low[from] == disc[from]) {
int top;
std::vector<int> scc;
do {
top = st.top();
st.pop();
scc.push_back(top);
} while(top != from);
sccs.push_back(scc);
}
}
int main() {
int n, m;
fin >> n >> m;
for(int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
graph[x].push_back(y);
}
for(int i = 1; i <= n; ++i) {
if(!low[i]) {
compute_sccs(i);
}
}
fout << sccs.size() << '\n';
for(std::vector<int> scc : sccs) {
for(int c : scc) {
fout << c << ' ';
}fout << '\n';
}
return 0;
}