Pagini recente » Cod sursa (job #1876247) | Cod sursa (job #416843) | Cod sursa (job #2048814) | Cod sursa (job #2201064) | Cod sursa (job #2574489)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMAX=100000;
int idx=1,n,m,lowest[NMAX],in_stack[NMAX],val[NMAX];
vector<int>g[NMAX],c;
stack<int>s;
vector<vector<int>>ans;
void tarjan(int node){
lowest[node]=val[node]=idx++;
s.push(node);
in_stack[node]=1;
for(auto y:g[node])
if(!val[y])
tarjan(y),lowest[node]=min(lowest[node],lowest[y]);
else if(in_stack[y])
lowest[node]=min(lowest[node],lowest[y]);
if(lowest[node]==val[node]){
int n;
c.clear();
do{
c.push_back(n=s.top());
in_stack[n]=0;
s.pop();
}while(n!=node);
ans.push_back(c);
}
}
int main()
{
in>>n>>m;
for(int i=1,a,b;i<=m;i++){
in>>a>>b;
g[a].push_back(b);
}
for(int i=1;i<=n;i++)
if(!val[i])
tarjan(i);
out<<ans.size()<<'\n';
for(int i=0;i<ans.size();i++){
for(auto y:ans[i])
out<<y<<" ";
out<<'\n';
}
return 0;
}