scc

scc.cpp

#include <iostream>
#include <map>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>


std::vector<std::vector<unsigned>> finishOrder;

void dfs(const std::multimap<unsigned, unsigned>& graph, unsigned n)
{
	std::vector<bool> discovered(n, false);
	for (unsigned s = 1; s < n; ++s)
	{
		if (discovered[s])
			continue;
		std::vector<unsigned>  fo;
		std::stack<unsigned> stack;
		stack.push(s);
		discovered[s] = true;

		while (!stack.empty())
		{
			auto current = stack.top();
			stack.pop();
			fo.push_back(current);
			auto r = graph.equal_range(current);
			for (auto i = r.first; i != r.second; ++i)
			{
				auto v = i->second;
				if (!(discovered[v]))
				{
					discovered[v] = true;
					stack.push(v);
				}
			}
		}
		finishOrder.push_back(fo);
	}
}

int main()
{
	std::multimap<unsigned, unsigned> g;
	decltype(g) g_rev;
	std::ifstream input_file("D:\\Playground\\clion\\SCC.txt");
	unsigned a, b;
	while (input_file >> a >> b)
	{
		g.insert({a, b});
		g_rev.insert({b,a});
	}
	auto n = a + 1;
	dfs(g_rev, n);

	std::vector<bool> discovered(n, false);
	std::vector<unsigned> scc_size;

	for (int i = finishOrder.size()-1; i >=0; --i)
	{
		auto&& fo = finishOrder[i];
		for(auto j=0;j<fo.size();j++)
		{
			unsigned size = 0;
			auto&& v = fo[j];

			if (discovered[v])
				continue;
			discovered[v] = true;
			std::stack<unsigned> stack;
			stack.push(v);
			size++;
			while (!stack.empty())
			{
				auto current = stack.top();
				stack.pop();


				auto r = g.equal_range(current);
				for (auto ii = r.first; ii != r.second; ++ii)
				{
					auto vv = ii->second;
					if (!(discovered[vv]))
					{
						size++;
						discovered[vv] = true;
						stack.push(vv);
					}
				}
			}
			scc_size.push_back(size);
		}
	}

	std::sort(scc_size.begin(), scc_size.end(), [](auto a,auto b)
	          {
		          return a > b;
	          });

	if (scc_size.size() >= 5)
	{
		for (auto j = 0; j < 5; j++)
		{
			std::cout << scc_size[j] << " ";
		}
	}
	else
	{
		for (auto&& s :scc_size)
		{
			std::cout << s << " ";
		}
	}


	return 0;
}