Cod sursa(job #1503629)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 16 octombrie 2015 17:28:13
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h>
#include <stack>
#include <vector>
#define MAX 100005
#define min(a, b) (((a) < (b)) ? (a) : (b))
using namespace std;

int n, m, i, j, x, y, index[MAX], lowlink[MAX], ind;
bool onStack[MAX];
stack<int> s;
vector<int> l[MAX], c;
vector< vector<int> > conex;

void tarjan(int x);

int main(){
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(i = 0; i < m; i++){
		scanf("%d%d", &x, &y);
		l[x].push_back(y);
	}

	for(i = 1; i <= n; i++)
		if(!index[i])
			tarjan(i);

	printf("%d\n", conex.size());
	for(i = 0; i < conex.size(); i++){
		for(j = 0; j < conex[i].size(); j++)
			printf("%d ", conex[i][j]);
		printf("\n");
	}
	return 0;
}

void tarjan(int x){
	s.push(x);
	lowlink[x] = index[x] = ind++;
	onStack[x] = 1;

	for(int i = 0; i < l[x].size(); i++)
		if(!index[l[x][i]]){
			tarjan(l[x][i]);
			lowlink[x] = min(lowlink[x], lowlink[l[x][i]]);
		}
		else
			lowlink[x] = min(lowlink[x], index[l[x][i]]);

	if(lowlink[x] == index[x]){
		int w;
		c.clear();
		do{
			w = s.top(), s.pop();
			c.push_back(w);
		}while(w != x);
		conex.push_back(c);
	}
}