Pagini recente » Cod sursa (job #340395) | Cod sursa (job #1516171) | Cod sursa (job #2313313) | Cod sursa (job #474190) | Cod sursa (job #2734286)
#include <bits/stdc++.h>
#define NMAX 100000
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
int n,m,x,y;
vector<int> G[NMAX+5],aux;
vector<vector<int>> comp;
int low[NMAX+5],ind[NMAX+5];
int st[NMAX+5],top;
int inst[NMAX+5];
int idx;
void tarjan(int nod){
low[nod]=ind[nod]=++idx;
st[++top]=nod;
inst[nod]=1;
for(auto y:G[nod]){
if(ind[y]==0){
tarjan(y);
low[nod]=min(low[nod],low[y]);
}else if(inst[y]){
low[nod]=min(low[nod],low[y]);
}
}
if(low[nod]==ind[nod]){
aux.clear();
while(top&&st[top]!=nod){
aux.push_back(st[top]);
inst[st[top]]=0;
top--;
}
aux.push_back(st[top]);
inst[st[top]]=0;
top--;
sort(aux.begin(),aux.end());
comp.push_back(aux);
}
}
int main(){
fi>>n>>m;
for(int i=1;i<=m;i++){
fi>>x>>y;
G[x].push_back(y);
}
for(int i=1;i<=n;i++){
ind[i]=0;
}
for(int i=1;i<=n;i++){
if(!ind[i]){
tarjan(i);
}
}
sort(comp.begin(),comp.end());
fo<<comp.size()<<'\n';
for(auto c:comp){
for(auto v:c){
fo<<v<<' ';
}
fo<<'\n';
}
fi.close();
fo.close();
}