Cod sursa(job #1499520)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 10 octombrie 2015 18:57:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 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, ind = 1, index[MAX], lowlink[MAX];
bool onStack[MAX];
vector<int> l[MAX], c;
vector< vector<int> > conex;
stack<int> s;

void ctc(int v);

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])
			ctc(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 ctc(int v){
	int w;
	index[v] = ind;
	lowlink[v] = ind++;
	s.push(v);
	onStack[v] = 1;

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

	if(lowlink[v] == index[v]){
		do{
			w = s.top();
			s.pop();
			onStack[w] = 0;
			c.push_back(w);
		}while(v != w);
		conex.push_back(c);
		c.clear();
	}
}