Cod sursa(job #797915)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 15 octombrie 2012 10:14:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#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;
}