Cod sursa(job #2405833)

Utilizator juganaru.calin@outlook.comJuganaru Calin [email protected] Data 15 aprilie 2019 00:15:44
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.24 kb
#include <fstream>
#include <vector>
#include <stack>
#include <unordered_set>

using namespace std;

void dfs(vector<vector<int>>& graph,
		 const int& node, const int& parent,
		 vector<int>& depth, vector<int>& low_point,
		 stack<pair<int, int>>& vertex_stack,
		 vector<unordered_set<int>>& components)
{
	static auto TIME = 0;
	depth[node] = low_point[node] = ++TIME;
    auto children = 0;

    for (auto&& son: graph[node])
    {
		if (!depth[son])
		{
            ++children;
            vertex_stack.push({node, son});
            dfs(graph, son, node, depth, low_point, vertex_stack, components);
            low_point[node] = min(low_point[node], low_point[son]);

            if (!parent && children > 1)
			{
				components.push_back(unordered_set<int>());
				while (true)
				{
					auto x = vertex_stack.top().first;
					auto y = vertex_stack.top().second;
					vertex_stack.pop();
					components.back().insert({x, y});
					if (x == node && y == son) return;
				}
			}

			if (parent && low_point[son] >= depth[node])
			{
				components.push_back(unordered_set<int>());
				while (true)
				{
					auto x = vertex_stack.top().first;
					auto y = vertex_stack.top().second;
					vertex_stack.pop();
					components.back().insert({x, y});
					if (x == node && y == son) return;
				}
			}
		}
		else if (parent != son && depth[son] < low_point[node])
		{
			low_point[node] = depth[son];
			vertex_stack.push({node, son});
		}
	}
}

int main()
{
    auto input = ifstream("biconex.in");
    auto output = ofstream("biconex.out");

	int N, M, x, y;	input >> N >> M;

	auto graph = vector<vector<int>>(N + 1);
	auto components = vector<unordered_set<int>>();
	auto vertex_stack = stack<pair<int, int>>();
	auto depth = vector<int>(N + 1), low_point = depth;

    while (M--)
    {
        input >> x >> y;
        graph[x].push_back(y);
		graph[y].push_back(x);
    }

	dfs(graph, 1, 0, depth, low_point, vertex_stack, components);
	components.push_back(unordered_set<int>());
	while (!vertex_stack.empty())
	{
		auto [x, y] = vertex_stack.top();
		vertex_stack.pop();
		components.back().insert({x, y});
	}

	output << components.size() << endl;
	for (auto&& comp: components)
    {
        for(auto&& node: comp)
            output << node << ' ';
		output << endl;
    }
}