Cod sursa(job #843757)

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

#define MAXN 100001

using namespace std;

int M,N;

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

bool visited[MAXN];


void dfs(int nod)
{
	visited[nod] = true;
	vector<int>::iterator it;
	for(it = vecini[nod].begin() ; it != vecini[nod].end(); it++){
		if( !visited[*it] )
			dfs(*it);
	}
	
	st.push(nod);	
}

void dfsT(int nod, vector<int> *solution)
{
	solution->push_back(nod);
	visited[nod] = true;
	
	vector<int>::iterator it;
	for(it = veciniT[nod].begin() ; it != veciniT[nod].end(); it++){
		if( !visited[*it] )
			dfsT(*it, solution);
	}
}

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);
		veciniT[right].push_back(left);
	}
	
	for(i=1;i<=N;i++){
		if( !visited[i] )
			dfs(i);
	}
	
	for(i=1;i<=N;i++)
		visited[i] = false;
	
	int nod;
	while( !st.empty() ){
		nod = st.top();
		st.pop();
		
		if( !visited[nod] ){
			vector<int> solutie;
			dfsT(nod, &solutie);
			componente.push_back(solutie);
		}		
	}
	
	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;
}