Cod sursa(job #843767)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 28 decembrie 2012 13:15:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <stdio.h>
#include <vector>
#include <stack>

#define MAXN 100001

using namespace std;

int M,N;

vector<int> vecini[MAXN];
stack<int>	st;
vector<vector<int> > componente;

int timp[MAXN];
int lowlink[MAXN];
int timp_curent = 1;
int tarjanel_id[MAXN];

int tarjanel_id_count = 0;

int min( int x, int y)
{
	if( x < y )
		return x;
	else
		return y;
}

void tarjan(int nod)
{	
	timp[nod] = timp_curent++;
	lowlink[nod] = nod;
	tarjanel_id[nod] = tarjanel_id_count;

	st.push(nod);
	vector<int>::iterator it;
	for(it=vecini[nod].begin(); it!=vecini[nod].end();it++){
		if( timp[*it] == 0 ){
			tarjan(*it);
			if( timp[lowlink[*it]] < timp[lowlink[nod]] )
				lowlink[nod] = lowlink[*it];
		}
		else if( tarjanel_id[*it] == tarjanel_id_count ){
			if( timp[lowlink[*it]] < timp[lowlink[nod]] )
				lowlink[nod] = lowlink[*it];			
		}
	}
	
	if( lowlink[nod] == nod ){
		vector<int> solutie;
		solutie.push_back(nod);
		int i;
		while( (i=st.top()) != nod){
			solutie.push_back(i);
			st.pop();
		}
		st.pop();
		
		componente.push_back(solutie);
	}
}

int main(int argc, char* argv[])
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	
	scanf("%d %d",&N,&M);
	
	int i, left, right;
	for(i=0;i<M;i++){
		scanf("%d %d",&left,&right);
		vecini[left].push_back(right);
	}
	
	for(i=1;i<=N;i++){
		tarjanel_id_count++;
		if( timp[i] == 0 )
			tarjan(i);
	}
	
	vector<vector<int> >::iterator itsol;
	vector<int>::iterator itval;
	
	printf("%d\n",componente.size());
	for(itsol=componente.begin(); itsol != componente.end(); itsol++){
		for(itval = itsol->begin(); itval != itsol->end(); itval++){
			printf("%d ",*itval);
		}
		printf("\n");
	}
	
	return 0;
}