Pagini recente » Cod sursa (job #73608) | Cod sursa (job #1815722) | Cod sursa (job #3249804) | Cod sursa (job #1985369) | Cod sursa (job #2538592)
#include<iostream>
#include<fstream>
#include<bitset>
#include<vector>
#include<stack>
using namespace std;
int n,ids[50010],low[50010],id=1,ctc=0;
vector <int> ve[50010];
vector <int> ct[50010];
stack <int> S;
bitset <50010> peStiva;
void dfs(int s){
peStiva[s]=1;
S.push(s);
ids[s]=low[s]=id++;
int i,nv,no;
for(i=0;i<ve[s].size();i++){
nv=ve[s][i];
if(ids[nv]==0) dfs(nv);
if(peStiva[nv]) low[s]=min(low[s],low[nv]);
}
if(low[s]==ids[s]){
ctc++;
do{
no=S.top();
//cout<<no<<endl;
S.pop();
ct[ctc].push_back(no);
peStiva[no]=0;
}while(no!=s);
cout<<endl;
}
}
int main(){
ifstream f("ctc.in");
int m,i,x,y,j; f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y;
ve[x].push_back(y);
}
f.close();
for(i=1;i<=n;i++)
if(ids[i]==0) dfs(i);
f.close();
ofstream o("ctc.out");
o<<ctc<<endl;
for(i=1;i<=ctc;i++){
for(j=0;j<ct[ctc].size();j++)
o<<ct[i][j]<<" ";
o<<endl;
}
o.close();
}