Cod sursa(job #1766060)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 27 septembrie 2016 13:09:31
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <stack>
#include <vector>

std::ifstream mama("ctc.in");
std::ofstream tata("ctc.out");

std::vector <int> v[100001];
std::vector <std::vector <int> > components;
std::stack <int> s;

int vindex[100001];
int l[100001];
bool onStack[100001];
int n;
int m;
int counterIndex;

void
go(int node)
{
	int vertex;
	int size;

	vindex[node] = counterIndex;
	l[node] = counterIndex;
	++counterIndex;
	s.push(node);
	onStack[node] = true;

	for (int i = 0; i < (int)v[node].size(); ++i)
	{
		if (not vindex[v[node][i]])
		{
			go(v[node][i]);
			if (l[node] > l[v[node][i]])
			{
				l[node] = l[v[node][i]];
			}
		}
		else
		{
			if (l[node] > vindex[v[node][i]])
			{
				l[node] = vindex[v[node][i]];
			}
		}
	}

	if (l[node] == vindex[node])
	{
		components.push_back(std::vector <int> ());
		size = (int)components.size() - 1;
		do
		{
			vertex = s.top();
			s.pop();

			components[size].push_back(vertex);
		} while (vertex != node);
	}
}

int main()
{
	mama >> n;
	mama >> m;

	for (int i = 0, a, b; i < m; ++i)
	{
		mama >> a >> b;
		v[a].push_back(b);
	}

	counterIndex = 1;
	for (int i = 1; i <= n; ++i)
	{
		if (not vindex[i])
		{
			go(i);
		}
	}

	tata << components.size() << '\n';

	for (const auto& comp : components)
	{
		for (const auto& it : comp)
		{
			tata << it << ' ';
		}

		tata << '\n';
	}

	return 0;
}