Cod sursa(job #1458516)

Utilizator glbglGeorgiana bgl glbgl Data 7 iulie 2015 18:06:02
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <stdio.h>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

#define UNDEF -1

using namespace std;

int N, M, nr = 0, index = 0;
vector< vector<int> > neigh;
vector< vector<int> > components;
vector<int> indx, lowlink;
vector<bool> in_stack;
stack<int> st;

ifstream in("ctc.in");
ofstream out("ctc.out");

void read(){

	in >> N >> M;

	in_stack.resize(N+1);

	indx.resize(N+1);
	indx.assign(N+1, UNDEF);
	lowlink.resize(N+1);

	for(int i = 0; i <= N; ++i){
		vector<int> v;
		neigh.push_back(v);
		components.push_back(v);
	}

	int x, y;
	for(int i = 0; i < M; ++i){
		in >> x >> y;
		neigh[x].push_back(y);
	}
}


void Tarjan(int u){

	indx[u] = index;
	lowlink[u] = index;
	index = index + 1;
	st.push(u);
	in_stack[u] = true;

	int v;

	for(unsigned int i = 0; i < neigh[u].size(); ++i){
		v = neigh[u][i];
		if(indx[v] == UNDEF){	
			Tarjan(v);
			lowlink[u] = min(lowlink[u], lowlink[v]);
		}
		else if(in_stack[v] == true)
			lowlink[u] = min(lowlink[u], indx[v]);
	}
	
	if(lowlink[u] == indx[u]){
		do{
			v = st.top();
			st.pop();
			in_stack[v] = false;
			components[nr].push_back(v);
		} while(v != u);

		nr++;
	}
	
}


void write(){

	out << nr << "\n";
	for(int i = 0; i < nr; ++i){
		for(unsigned int j = 0; j < components[i].size(); ++j){
			out << components[i][j] << " ";
		}
		out << "\n";
	}
}


int main(){

	read();

	for(int i = 1; i <= N; ++i){
		if(indx[i] == UNDEF)
			Tarjan(i);
	}

	write();
}