Cod sursa(job #1070320)

Utilizator dm1sevenDan Marius dm1seven Data 31 decembrie 2013 16:56:33
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.24 kb
#include <fstream>
#include <sstream>
#include <deque>
#include <algorithm>
using namespace std;

void tarjan(int v, int N, deque<int>* adj, 
	int current_index, int* index, int* lowlink, deque<int>& S, char* is_in_queue, 
	int& component_id,
	stringstream* ss)
{
	index[v] = ++current_index; //assign a new index to the node; mark the node as read
	lowlink[v] = current_index; //the initial guess for the components
	S.push_back(v);
	is_in_queue[v] = 1;

	//parse the adjacency list of the node
	for (deque<int>::iterator it = adj[v].begin(); it != adj[v].end(); it++) {
		int w = *it;
		//check if w does not have an index or it is already indexed and is in the queue
		if (index[w] == 0) {
			tarjan(w, N, adj, current_index, index, lowlink, S, is_in_queue, component_id, ss);
			//update the lowlink of the current node
			lowlink[v] = min(lowlink[v], lowlink[w]);
		}
		else if (is_in_queue[w]) {
			lowlink[v] = min(lowlink[v], lowlink[w]);
		}
	}

	//check if the current node is the root of a strong connex component
	if (lowlink[v] == index[v]) {
		component_id++;
		int u;
		while ( (u = S.back()) != v) {
			S.pop_back();
			is_in_queue[u] = 0;
			ss[component_id] << u << ' ';
		}
		//once more for v
		S.pop_back();
		is_in_queue[v] = 0;
		ss[component_id] << v << ' ';
	}
}

//int e_026_componente_tare_conexe_tarjan()
int main() 
{
	string in_file = "ctc.in";
	string out_file = "ctc.out";

	int N, M;
	const int MAX_N = 10000;

	//the adjacency list
	deque<int> adj[MAX_N + 1];

	ifstream ifs(in_file);
	ifs >> N >> M;
	for (int k = 1; k <= M; k++)
	{
		int v1, v2;
		ifs >> v1 >> v2;
		adj[v1].push_back(v2);
	}
	ifs.close();

	int index[MAX_N + 1], lowlink[MAX_N + 1];
	char is_in_queue[MAX_N + 1];
	stringstream ss[MAX_N + 1];
	for (int v = 1; v <= N; v++) { index[v] = 0;  is_in_queue[v] = 0; }
	deque<int> S;
	int current_index = 0, component_id = 0;
	for (int v = 1; v <= N; v++) {
		if (index[v] == 0) tarjan(v, N, adj, current_index, index, lowlink, S, is_in_queue, component_id, ss);
	}

	int no_of_components = component_id;
	ofstream ofs(out_file);
	ofs << no_of_components << endl;
	for (int c = 1; c <= no_of_components; c++) ofs << ss[c].str() << endl;
	ofs.close();

	return 0;
}