Pagini recente » Cod sursa (job #949768) | Cod sursa (job #1091476) | Cod sursa (job #1055311) | Cod sursa (job #272286) | Cod sursa (job #996760)
Cod sursa(job #996760)
#include <fstream>
#include <vector>
#include <list>
#include <stack>
using std::stack;
using std::vector;
using std::list;
void strongconnect(unsigned v, unsigned &cind, stack<unsigned> &S,
vector<unsigned> &index, vector<unsigned> &lowlink, vector<bool> &instack,
list< list<unsigned> > &scc,
unsigned N, const vector< list<unsigned> > &Adj){
index[v]=lowlink[v]=cind++;
S.push(v); instack[v]=true;
for(list<unsigned>::const_iterator w=Adj[v].begin();w!=Adj[v].end();++w){
if(index[*w]==0){
strongconnect(*w,cind,S,index,lowlink,instack,scc,N,Adj);
if(lowlink[v]>lowlink[*w]) lowlink[v]=lowlink[*w];
}
else if(instack[*w]&&lowlink[v]>index[*w]) lowlink[v]=index[*w];
}
if(lowlink[v]==index[v]){
list<unsigned> temp;
unsigned w;
do{
w=S.top(); S.pop(); instack[w]=false;
temp.push_back(w);
}while(w!=v);
scc.push_back(temp);
}
}
int main(){
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
unsigned N,M;
fin>>N>>M;
vector< list<unsigned> > Adj(N+1);
for(unsigned i=0;i<M;++i){unsigned x,y; fin>>x>>y; Adj[x].push_back(y);}
list< list<unsigned> > scc;
unsigned cind=1;
stack<unsigned> S;
vector<unsigned> index(N+1,0);
vector<unsigned> lowlink(N+1,0);
vector<bool> instack(N+1,0);
for(unsigned i=1;i<=N;++i)
if(index[i]==0) strongconnect(i,cind,S,index,lowlink,instack,scc,N,Adj);
fout<<scc.size()<<'\n';
for(list<list<unsigned> >::iterator i=scc.begin();i!=scc.end();++i){
for(list<unsigned>::iterator j=i->begin();j!=i->end();++j) fout<<*j<<' ';
fout<<'\n';
}
}