Cod sursa(job #526943)

Utilizator Gaby_mMititelu Gabriel Gaby_m Data 29 ianuarie 2011 23:27:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include<cstdio>
#include<stack>
using namespace std;

struct list {
	int neigh;
	list *next;
};


list *graf[100001];
list *grafRev[100001];
list *compCon[100001];

bool viz[100001];
int N, M;
int compconex;
stack<int> stackNodes;


void readData() {
	
	scanf("%d %d", &N, &M);
	int x, y;
	for (int i = 0; i < M; i++) {
		scanf("%d %d ", &x, &y);

		list *aux = new list;
		aux->neigh = y;
		aux->next = graf[x];
		graf[x] = aux;

		aux = new list;
		aux->neigh = x;
		aux->next = grafRev[y];
		grafRev[y] = aux;
	}
}


void dfs(int source){
	viz[source] = 1;
	list *aux = graf[source];
	while (aux) {
		if (!viz[aux->neigh]) {			
			dfs(aux->neigh);
		}
		aux = aux->next;
	}
	stackNodes.push(source);
}


void dft(int source){
	viz[source] = 0;

	
	list *add = new list;
	add->neigh = source;
	add->next = compCon[compconex];
	compCon[compconex] = add;

	list *aux = grafRev[source];
	while (aux) {
		if (viz[aux->neigh]) {			
			dft(aux->neigh);
		}
		aux = aux->next;
	}
	stackNodes.push(source);
}



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

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

	int x;
	compconex = 0;
	while (!stackNodes.empty()) {
		x = stackNodes.top();
		stackNodes.pop();
		if (viz[x]){			
			dft(x);
			compconex++;
		}
	}

	printf("%d\n",compconex);
	for (int i = 0; i < compconex; i++) {
		list *aux = compCon[i];
		while (aux){
			printf("%d ", aux->neigh);
			aux = aux->next;
		}
		printf("\n");
	}

	
	return 0;
}