Pagini recente » Cod sursa (job #2120151) | Cod sursa (job #1179314) | Cod sursa (job #2623627) | Cod sursa (job #3312390) | Cod sursa (job #3331443)
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<int> disc;
vector<int> low;
vector<bool> inSt;
vector<vector<int>> res;
stack<int> st;
int timer;
void dfs(int n){
st.push(n);
inSt[n]=true;
timer++;
disc[n]=timer;
low[n]=timer;
for(int v: adj[n]){
if(disc[v]==-1){
dfs(v);
low[n]=min(low[n],low[v]);
}
else if(inSt[v]){
low[n]=min(low[n],disc[v]);
}
}
if(low[n]==disc[n]){
vector<int> r;
while((!st.empty()) && st.top()!=n){
r.push_back(st.top());
inSt[st.top()]=false;
st.pop();
}
r.push_back(n);
inSt[n]=false;
st.pop();
res.push_back(r);
}
return;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int N,M;cin>>N>>M;
adj.resize(N,{});
disc.resize(N,-1);
low.resize(N);
inSt.resize(N,false);
int a,b;
for(int i=0;i<M;i++){
cin>>a>>b;a--;b--;
adj[a].push_back(b);
}
timer=0;
for(int i=0;i<N;i++){
if(disc[i]==-1){
dfs(i);
}
}
cout<<res.size()<<'\n';
for(auto r: res){
for(auto i: r){
cout<<i+1<<" ";
}
cout<<'\n';
}
}