Pagini recente » Cod sursa (job #1499170) | Cod sursa (job #249450) | Cod sursa (job #503741) | Cod sursa (job #3159552) | Cod sursa (job #633241)
Cod sursa(job #633241)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N=100001;
const int M=200001;
int n,m,nrsol,index[N],low[N],nrindex;
vector <int> edge[N], sol[M];
stack <int> stiva;
bool viz[N];
void citire(){
int a,b;
int i;
in>>n>>m;
for(i=1;i<=m;i++){
in>>a>>b;
edge[a].push_back(b);
}
}
inline int min(int a,int b){
return a<b? a: b;
}
void Tarjan(int x){
int i,y;
++nrindex;
viz[x]=true;
index[x]=nrindex;
low[x]=nrindex;
stiva.push(x);
for(i=0;i<edge[x].size();++i){
y=edge[x][i];
if(!viz[y]){
Tarjan(y);
low[x]=min(low[x],low[y]);
}
else{
low[x]=min(low[x],index[y]);
}
}
if(index[x]==low[x]){
nrsol++;
while(stiva.top()!=x){
sol[nrsol].push_back(stiva.top());
stiva.pop();
}
sol[nrsol].push_back(stiva.top());
stiva.pop();
}
}
void rezolvare(){
int i;
for(i=1;i<=n;i++){
if(!viz[i])
Tarjan(i);
}
}
void scriere(){
int i,j;
out<<nrsol<<"\n";
for(i=1;i<=nrsol;++i){
for(j=0;j<sol[i].size();++j){
out<<sol[i][j]<<" ";
}
out<<"\n";
}
}
int main(){
citire();
rezolvare();
scriere();
return 0;
}