Cod sursa(job #574128)

Utilizator TrumpCardPopescu Silviu TrumpCard Data 6 aprilie 2011 20:49:58
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 100000
using namespace std;
vector <int> G[NMAX], ctc;
vector < vector <int> > printer;
int N, M, idx[NMAX], lowlink[NMAX], ind;
stack <int> S;
bool in_stack[NMAX];
void tarjan(int nod){
	ind++;
	idx[nod] = lowlink[nod] = ind;
	S.push(nod);
	in_stack[nod] = true;
	for (int i = 0; i < G[nod].size(); i++)
		if(!idx[i]){
			tarjan(i);
			lowlink[nod] = min(lowlink[nod], lowlink[i]);
		}
		else{
			if (in_stack[i])
				lowlink[nod] = min(lowlink[nod], lowlink[i]);
		}
	if (idx[nod] == lowlink[nod]){
		int aux;
		ctc.clear();
		do {
			aux = S.top();
			S.pop();
			in_stack[aux] = false;
			ctc.push_back(aux);
		} while (aux != nod);
		printer.push_back(ctc);
	}
}
int main(){
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	int n, m;
	std::cin >> n >> m;
	for (int i = 0; i < m; i++){
		int x, y;
		std::cin >> x >> y;
		G[x].push_back(y);
	}
	for (int i = 0; i < n; i++)
		if (!idx[i])
			tarjan(i);
	n = printer.size();
	std::cout << n << "\n";
	for (int i = 0; i < n; i++){
		m = printer[i].size();
		for (int j = 0; j < m; j++)
			std::cout << printer[i][j]<< " ";
		std::cout << "\n";
	}	
	return 0;
}