Pagini recente » Cod sursa (job #2207898) | Cod sursa (job #2169753) | Cod sursa (job #2259068) | Cod sursa (job #1045961) | Cod sursa (job #2207247)
#include <bits/stdc++.h>
using namespace std;
ofstream fout("ctc.out");
ifstream fin("ctc.in");
const int NMax = 100010;
vector<vector<int> > ans;
vector<int> G[NMax];
int d[NMax];
int low[NMax];
stack<int> st;
bool onstack[NMax];
int n, m, x, y;
int indexi;
void dfs(int node){
d[node] = ++indexi;
low[node] = indexi;
onstack[node] = true;
st.push(node);
indexi++;
for(auto next : G[node]){
if(!d[next]) dfs(next), low[node] = min(low[node], low[next]);
else if(onstack[next]) low[node] = min(low[node], low[next]);
}
if(d[node] == low[node]){
ans.push_back(vector<int>());
int v;
do{
v = st.top();
ans[ans.size() - 1].push_back(v);
onstack[v] = false;
st.pop();
}while(v != node);
}
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= m; i++){
fin >> x >> y;
G[x].push_back(y);
}
for(int i = 1; i <= n; i++){
if(d[i] == 0)
dfs(i);
}
fout << ans.size()<< '\n';
for(int i = 0; i < ans.size(); i++){
for(int j = 0; j < ans[i].size(); j++){
fout << ans[i][j] << ' ';
}
fout << '\n';
}
return 0;
}