Pagini recente » Cod sursa (job #723166) | Cod sursa (job #1763230) | Cod sursa (job #1986742) | Cod sursa (job #2030742) | Cod sursa (job #2760881)
#include <bits/stdc++.h>
#define nmax 100001
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
struct node{
int index,lowlink;
node(){
index=lowlink=0;
}
};
int ind=0;
vector<node> noduri(nmax);
vector<int> graf[nmax];
vector<bool> viz(nmax,0);
stack<int> s;
vector<vector<int>> ans;
vector<bool> onStack(nmax,0);
void dfs(int nod){
noduri[nod].index=noduri[nod].lowlink=ind++;
s.push(nod);
onStack[nod]=1;
viz[nod]=1;
for(auto i:graf[nod]){
if(!viz[i]){
dfs(i);
noduri[nod].lowlink=min(noduri[i].lowlink,noduri[nod].lowlink);
}else if(onStack[i])noduri[nod].lowlink=min(noduri[i].index,noduri[nod].lowlink);
}
if(noduri[nod].index==noduri[nod].lowlink){
vector<int> tmp;
int i;
do{
i=s.top();
s.pop();
onStack[i]=0;
tmp.push_back(i);
}while(i!=nod);
ans.push_back(tmp);
}
}
int main(){
int n,m;
in>>n>>m;
for(;m;m--){
int x,y;
in>>x>>y;
graf[x].push_back(y);
}
for(int i=1;i<=n;i++){
if(!viz[i])dfs(i);
}
out<<ans.size()<<'\n';
for(auto i:ans){
for(auto j:i){
out<<j<<' ';
}
out<<'\n';
}
}