Pagini recente » Cod sursa (job #1798026) | Cod sursa (job #2077647) | Cod sursa (job #2891789) | Cod sursa (job #248390) | Cod sursa (job #2237834)
#include <fstream>
#include <vector>
#include <stack>
std::ifstream cin("ctc.in");
std::ofstream cout("ctc.out");
#define maxn 200020
#define inf 50000
#define Min(a,b) (a<b)?a:b
using namespace std;
vector <int> muc[maxn],com;
vector <vector <int>> C;
int viz[maxn],in_stack[maxn],lowlink[maxn];
stack <int> S;
int N,M,indecs=1;
void tarjan(int x){
viz[x]=lowlink[x]=indecs;
indecs++;
S.push(x); in_stack[x]=1;
for(vector <int>::iterator it=muc[x].begin();it!=muc[x].end();it++){
if(!viz[*it]){
tarjan(*it);
lowlink[x]=Min(lowlink[x],lowlink[*it]);
}else if(in_stack[*it])
lowlink[x]=Min(lowlink[x],lowlink[*it]);
}
if(viz[x]==lowlink[x]){
com.clear();
int nod;
do{
com.push_back(nod=S.top());
S.pop();
in_stack[nod]=0;
}while(x!=nod);
C.push_back(com);
}
}
int main()
{
int x,y;
cin>>N>>M;
for(;M--;){
cin>>x>>y;
muc[x].push_back(y);
}
for(int i=1;i<=N;i++)
if(!viz[i])
tarjan(i);
cout<<C.size()<<'\n';
for(unsigned int i=0;i<C.size();i++){
for(vector <int>::iterator it=C[i].begin();it!=C[i].end();it++)
cout<<*it<<' ';
cout<<'\n';
}
}