Cod sursa(job #1380185)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 6 martie 2015 22:50:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb

#include <fstream>
#include <vector>
#include <bitset>
#include <stack>

const int MAX_N(100001);

int n, Scc;
std::vector<int> Graph [MAX_N], Transpose [MAX_N], Components [MAX_N];
std::bitset<MAX_N> Mark;
std::stack<int> Stack;

inline void Read (void)
{
	std::ifstream input("ctc.in");
	int m;
	input >> n >> m;
	int x, y;
	while (m)
	{
		input >> x >> y;
		Graph[x].push_back(y);
		Transpose[y].push_back(x);
		--m;
	}
	input.close();
}

inline void Print (void)
{
	std::ofstream output("ctc.out");
	output << Scc << '\n';
	for (int i(1) ; i <= Scc ; ++i)
	{
		for (unsigned int j(0) ; j < Components[i].size() ; ++j)
			output << Components[i][j] << ' ';
		output.put('\n');
	}
	output.close();
}

void Toposort (int node)
{
	if (!Mark[node])
	{
		Mark[node] = true;
		for (unsigned int i(0) ; i < Graph[node].size() ; ++i)
			Toposort(Graph[node][i]);
		Stack.push(node);
	}
}

void DepthFirstSearch (int node)
{
	if (!Mark[node])
	{
		Components[Scc].push_back(node);
		Mark[node] = true;
		for (unsigned int i(0) ; i < Transpose[node].size() ; ++i)
			DepthFirstSearch(Transpose[node][i]);
	}
}

inline void Kosaraju (void)
{
	for (int i(1) ; i <= n ; ++i)
		Toposort(i);
	Mark.reset();
	while (!Stack.empty())
	{
		if (!Mark[Stack.top()])
		{
			++Scc;
			DepthFirstSearch(Stack.top());
		}
		Stack.pop();
	}
}

int main (void)
{
	Read();
	Kosaraju();
	Print();
	return 0;
}