Pagini recente » Cod sursa (job #2468096) | Cod sursa (job #2701180) | Cod sursa (job #1419433) | Cod sursa (job #90081) | Cod sursa (job #2666601)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
typedef vector<int> vi;
typedef vector<bool> vb;
const int oo=INT_MAX/2;
int n,m,k;
vector<vector<int>> g;
// vector<vector<int>> gr; // graph
vector<vector<int>> con;
vector<int> rd;
vector<bool> onStk;
deque<int> stk;
int tarjan(int cr, int dep=1){
rd[cr]=dep;
onStk[cr]=1;
stk.push_back(cr);
cout<<"mih\n";
for(int nx:g[cr]){
if(rd[nx]==oo)
rd[cr]=min(rd[cr],tarjan(nx,dep+1));
else if(onStk[nx])
rd[cr]=min(rd[cr],rd[nx]);
}
if(dep==rd[cr]){
con.push_back(vector<int>());
do {
cout<<stk.back()<<"\n";
con[con.size()-1].push_back(stk.back());
onStk[stk.back()]=0;
stk.pop_back();
}
while(stk.back()!=cr);
}
return rd[cr];
}
int main(){
fin>>n>>m;
g.resize(n+1), rd.resize(n+1,oo), onStk.resize(n+1,0);
for(int i=m;i--;){
int x,y;
fin>>x>>y;
g[x].push_back(y);
}
tarjan(1);
fout<<con.size()<<"\n";
for(int i=0;i<con.size();++i){
for(int j=0; j<con[i].size();++j)
fout<<con[i][j]<<" ";
fout<<"\n";
}
}