Pagini recente » Cod sursa (job #1111601) | Cod sursa (job #3195987) | Cod sursa (job #2765800) | Cod sursa (job #2368136) | Cod sursa (job #3243159)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int const NMAX = 1e5;
vector <int> g[1 + NMAX];
int indSize;
int ind[1 + NMAX];
int lowlink[1 + NMAX];
int onStack[1 + NMAX];
stack <int> st;
int ansSize = 0;
vector <int> ans[1 + NMAX];
void computeTarjan(int node) {
indSize++;
ind[node] = indSize;
lowlink[node] = ind[node];
onStack[node] = true;
st.push(node);
for(int i = 0;i < g[node].size();i++) {
int to = g[node][i];
if(ind[to] == 0) {
computeTarjan(to);
lowlink[node] = min(lowlink[node], lowlink[to]);
}else if(onStack[to] == true) {
lowlink[node] = min(lowlink[node], ind[to]);
}
}
if(lowlink[node] == ind[node]) {
ansSize++;
//cerr << node << '\n';
while(st.top() != node) {
//cerr << st.top() << ' ';
ans[ansSize].push_back(st.top());
onStack[st.top()] = false;
st.pop();
}
//cerr << st.top() << '\n';
ans[ansSize].push_back(node);
onStack[node] = false;
st.pop();
}
}
int main() {
int n, m;
in >> n >> m;
for(int i = 1;i <= m;i++) {
int a, b;
in >> a >> b;
g[a].push_back(b);
}
for(int i = 1;i <= n;i++) {
if(ind[i] == 0) {
computeTarjan(i);
}
}
out << ansSize << '\n';
for(int i = 1;i <= ansSize;i++) {
for(int j = 0;j < ans[i].size();j++) {
out << ans[i][j] << ' ';
}
out << '\n';
}
return 0;
}