Pagini recente » Cod sursa (job #247962) | Cod sursa (job #1184653) | Cod sursa (job #3244266) | Cod sursa (job #937799) | Cod sursa (job #2542972)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
int n,id=0,ids[100010],low[100010],ctc=0;
vector <int> v[100010],cc[100010];
stack <int> S;
bool onStack[100010];
void dfs(int k){
ids[k]=low[k]=++id; int nv,i;
S.push(k); onStack[k]=1;
for(nv=0;nv<v[k].size();nv++){
i=v[k][nv];
if(ids[i]==0){
dfs(i);
low[k]=min(low[k],low[i]);
}
else if(onStack[i]) low[k]=min(low[k],low[i]);
}
if(ids[k]==low[k]){
ctc++;
while(1){
cc[ctc].push_back(S.top());
onStack[S.top()]=0;
if(S.top()==k){
S.pop();
break;
}
S.pop();
}
}
}
int main(){
int i,m,x,y,j;
ifstream f("ctc.in");
f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y;
v[x].push_back(y);
}
f.close();
for(i=1;i<=n;i++)
if(ids[i]==0) dfs(i);
ofstream o("ctc.out");
o<<ctc<<endl;
for(i=1;i<=ctc;i++){
for(j=0;j<cc[i].size();j++)
o<<cc[i][j]<<" ";
o<<endl;
}
o.close();
}