Pagini recente » Cod sursa (job #1970065) | Cod sursa (job #1651875) | Diferente pentru schimbare-borland/alternativa intre reviziile 10 si 11 | Cod sursa (job #1700185) | Cod sursa (job #1968006)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct graf{
int nod;
graf*urm;
}*a[100001];
int n,m,i,index=1,ind[100001],ll[100001];
vector<int>con;
stack<int>s;
vector<vector<int>>C;
bool st[100001];
void add(int x,int y){
graf*f=new graf;
f->nod=y;
f->urm=a[x];
a[x]=f;
}
void scn(int k){
ind[k]=index;
ll[k]=index;
index++;
s.push(k);
st[k]=true;
graf*f=a[k];
while(f){
if(ind[f->nod]==0){
scn(f->nod);
ll[k]=min(ll[k],ll[f->nod]);}
else if(st[f->nod])
ll[k]=min(ll[k],ind[f->nod]);
f=f->urm;
}
if(ll[k]==ind[k]){
con.clear();
int w=0;
while(w!=k){
w=s.top();
con.push_back(w);
s.pop();
st[w]=false;
}
C.push_back(con);
}
}
int main(){
int x,y;
fin>>n>>m;
for(i=1;i<=m;i++){
fin>>x>>y;
add(x,y);
}
for(i=1;i<=n;i++)st[i]=false;
for(i=1;i<=n;i++){
if(ind[i]==0)scn(i);
}
x=C.size();
fout<<x<<endl;
for(i=0;i<x;i++){
y=C[i].size();
for(int j=0;j<y;j++)
fout<<C[i][j]<<' ';
fout<<endl;
}
return 0;
}