Cod sursa(job #1459437)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 9 iulie 2015 20:57:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <vector>
#define MAX 100005
#define min(a, b) (a < b ? a : b)
using namespace std;

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

void strongconnect(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++)
		index[i] = -1;

	for(i = 1; i <= n; i++)
		if(index[i] == -1)
			strongconnect(i);

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

	return 0;
}

void strongconnect(int v){
	s.push_back(v);
	lowlink[v] = index[v] = ind;
	ind++;
	onStack[v] = true;
	vector<int>::iterator it;
	for(it = l[v].begin(); it < l[v].end(); it++)
		if(index[*it] == -1){
			strongconnect(*it);
			lowlink[v] = min(lowlink[v], lowlink[*it]);
		}
		else if(onStack[*it])
			lowlink[v] = min(lowlink[v], index[*it]);

	if(lowlink[v] == index[v]){
		int w = 0;
		con.clear();
		do{
			w = s.back();
			con.push_back(w);
			onStack[w] = false;
			s.pop_back();
		}while(w != v);
		C.push_back(con);
	}
}