Cod sursa(job #2295587)

Utilizator cezar.plescaCezar Plesca cezar.plesca Data 3 decembrie 2018 19:29:41
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include<stdio.h>
#include<stdlib.h>

#include<vector>
#include<string>
using namespace std;

#define MAXN 100000
#define MAXM 200000

int M,N;
vector<int> L[MAXN+1];

bool viz[MAXN];

typedef struct nod{
	int index;
	int low;
	bool instack;
}nod;

nod V[MAXN+1];
int S[MAXN];
int stack;
int index=1;

int nbcomp;
vector<int> C[MAXN];

void componente(int nod){

	viz[nod]=true;

	V[nod].index = index;
	V[nod].low = index;
	V[nod].instack = true;
	index++; 

	S[stack]=nod;
    stack++;

	vector<int>::iterator it;
	int vecin;
	for(it=L[nod].begin();it!=L[nod].end();it++){		
		vecin=*it;
		if(!viz[vecin]){
			componente(vecin);
			if(V[nod].low > V[vecin].low)
				V[nod].low = V[vecin].low;
		}
		else{
			if(V[vecin].instack){ 
				if(V[nod].low > V[vecin].index)
					V[nod].low = V[vecin].index;
			}
		}
	}

	if (V[nod].low == V[nod].index){
		// start a new strongly connected component
		while(S[stack-1]!=nod){
			C[nbcomp].push_back(S[stack-1]);
			V[S[stack-1]].instack=false;
			stack--;
		}
		C[nbcomp].push_back(S[stack-1]);
		V[S[stack-1]].instack=false;
		stack--;

		nbcomp++;
	}        
}

int main(){
		
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);

	scanf("%d %d",&N,&M);

	int x,y;

	for(int i=0;i<M;i++){
		scanf("%d %d",&x,&y);
		L[x].push_back(y);
	}

	for(int i=1;i<=N;i++){
		if(!viz[i])
			componente(i);
	}

	printf("%d\n",nbcomp);

	vector<int>::iterator it;
	for(int i=0;i<nbcomp;i++){
		for(it=C[i].begin();it!=C[i].end();it++){
			printf("%d ",*it);
		}
		printf("\n");
	}

	return 0;
}