Cod sursa(job #1070376)

Utilizator dm1sevenDan Marius dm1seven Data 31 decembrie 2013 19:35:06
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <fstream>
#include <sstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

namespace e_026_componente_tare_conexe {

	const int MAX_N = 100000;
	int N;

	int *index, *lowlink;
	int current_index = 0, component_id = 0;
	char* is_in_queue;
	
	vector<int> adj[MAX_N + 1];
	
	stack<int> S;
	vector<vector<int>> SCCs;
	vector<int> scc;
	
	void tarjan(int v)
	{
		current_index++;
		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(v);
		is_in_queue[v] = 1;

		//parse the adjacency list of the node
		for (vector<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);
				//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++;
			scc.clear();
			int u;
			do {
				u = S.top();
				S.pop();
				is_in_queue[u] = 0;
				scc.push_back(u);
			} while (u != v);
			SCCs.push_back(scc);
		}
	}

}

//int e_026_componente_tare_conexe_tarjan()
int main() 
{
	using namespace e_026_componente_tare_conexe;

	string in_file = "ctc.in";
	string out_file = "ctc.out";

	int M;	
	
	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();

	index = new int[N+1], lowlink = new int[N+1];
	is_in_queue = new char[N+1];
	for (int v = 1; v <= N; v++) { index[v] = 0;  is_in_queue[v] = 0; }
	for (int v = 1; v <= N; v++) if (index[v] == 0) tarjan(v);

	int no_of_components = component_id;
	ofstream ofs(out_file);
	ofs << no_of_components << endl;
	for (int c = 0; c < no_of_components; c++) {
		vector<int>& scc = SCCs[c];
		for (vector<int>::iterator it = scc.begin(); it != scc.end(); it++) ofs << *it << ' ';
		ofs << endl;
	}
	ofs.close();

	//relsease the memory
	delete[] index;
	delete[] lowlink;
	delete[] is_in_queue;

	return 0;
}