Pagini recente » Cod sursa (job #1759544) | Cod sursa (job #687364) | Cod sursa (job #853838) | Cod sursa (job #1732479) | Cod sursa (job #996720)
Cod sursa(job #996720)
#include <fstream>
#include <vector>
#include <queue>
#include <list>
#include <stack>
typedef std::list< std::list<unsigned> > LLU_t;
typedef std::vector< std::queue<unsigned> > VQU_t;
void tarjan(LLU_t &scc, unsigned N, VQU_t &Adj){
std::stack<unsigned> TarjanStack, DfsStack;
std::vector<bool> instack(N+1,false);
std::vector<unsigned> index(N+1,0);
std::vector<unsigned> lowlink(N+1,0);
unsigned cind=1;
for(unsigned k=1;k<=N;++k) if(index[k]==0){
DfsStack.push(k);
while(!DfsStack.empty()){
unsigned &v=DfsStack.top();
if(index[v]==0){
TarjanStack.push(v); instack[v]=true;
index[v]=cind;
lowlink[v]=cind;
++cind;
}
bool cont=true;
while(!Adj[v].empty()&&cont){
if(index[Adj[v].front()]==0){
DfsStack.push(Adj[v].front());
cont=false;
}
else if(instack[Adj[v].front()]&&lowlink[v]>lowlink[Adj[v].front()])
lowlink[v]=lowlink[Adj[v].front()];
if (cont) Adj[v].pop();
}
if(!cont) continue;
if(lowlink[v]==index[v]){
std::list<unsigned> temp;
do{
temp.push_front(TarjanStack.top());
instack[TarjanStack.top()]=false;
TarjanStack.pop();
}while(temp.front()!=v);
scc.push_back(temp);
}
DfsStack.pop();
}
}
}
int main(){
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
unsigned N,M;
fin>>N>>M;
VQU_t Adj(N+1);
for(unsigned i=0;i<M;++i){unsigned x,y; fin>>x>>y; Adj[x].push(y);}
LLU_t scc;
tarjan(scc,N,Adj);
fout<<scc.size()<<'\n';
for(LLU_t::iterator i=scc.begin();i!=scc.end();++i){
for(std::list<unsigned>::iterator j=i->begin();j!=i->end();++j) fout<<*j<<' ';
fout<<'\n';
}
}