Pagini recente » Borderou de evaluare (job #1336934) | Cod sursa (job #2207220)
#include <bits/stdc++.h>
using namespace std;
ofstream fout("ctc.out");
ifstream fin("ctc.in");
const int NMax = 100010;
vector<vector<int> > ans;
int d[NMax];
int st[NMax];
int onstack[NMax];
int ctc[NMax];
int k;
vector<int> G[NMax];
int nr = 1;
int n, m, x, y;
int dfs(int node, int depth){
d[node] = depth;
st[++k] = node;
onstack[node] = true;
for(int i = 0; i < G[node].size();i++){
int next = G[node][i];
if(ctc[next]) continue;
if(!onstack[next]) d[node] = min(d[node], dfs(next, depth + 1));
else d[node] = min(d[node], d[next]);
}
if(d[node] == depth){
ans.push_back(vector<int>());
while(st[k] != node){
ans[ans.size() - 1].push_back(st[k]);
onstack[st[k]] = false;
ctc[st[k--]] = nr;
}
onstack[st[k]] = false;
ans[ans.size() - 1].push_back(st[k]);
ctc[st[k--]] = nr;
nr++;
}
return d[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(ctc[i] == 0){
dfs(i, 1);
}
}
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;
}