Pagini recente » Cod sursa (job #2161175) | Cod sursa (job #1185436) | Istoria paginii runda/o-n_logan/clasament | Cod sursa (job #432518) | Cod sursa (job #2405834)
#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 = vertex_stack.top().first;
auto y = vertex_stack.top().second;
vertex_stack.pop();
components.back().insert({x, y});
}
output << components.size() << endl;
for (auto&& comp: components)
{
for(auto&& node: comp)
output << node << ' ';
output << endl;
}
}