Pagini recente » Cod sursa (job #594696) | Cod sursa (job #2332509) | Cod sursa (job #2373594) | Cod sursa (job #1476273) | Cod sursa (job #797915)
Cod sursa(job #797915)
#include<fstream>
#include<stack>
#define dim 100005
#include<vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int>G[dim],sol[dim];
int n,m,ctc;
stack<int>st;
int i,j,x,y,v,next;
int viz[dim],low[dim];
inline int minim (int a,int b){
if(a<b)
return a;
return b;
}
void tarjan (int x ) {
next++;
viz[x]=next;
low[x]=next;
st.push(x);
for(int i=0;i<G[x].size();++i){
if(viz[G[x][i]]==0){
tarjan(G[x][i]);
low[x]=minim(low[x],low[G[x][i]]);
}
else
if(viz[G[x][i]]>0){
low[x]=minim(low[x],low[G[x][i]]);
}
}
if(low[x]==viz[x]){
ctc++;
do{
v=st.top();
st.pop();
viz[v]=-viz[v];
sol[ctc].push_back(v);
}while(x!=v);
}
}
int main () {
f>>n>>m;
for(i=1;i<=m;++i){
f>>x>>y;
G[x].push_back(y);
}
for(i=1;i<=n;++i)
if(!viz[i])
tarjan(i);
g<<ctc<<"\n";
for(int i=1;i<=ctc;++i){
for(int j=0;j<sol[i].size();++j)
g<<sol[i][j]<<" ";
g<<"\n";
}
return 0;
}