Cod sursa(job #3375003)

Utilizator TLuca2021Teodorescu Luca Nicolae TLuca2021 Data 9 noiembrie 2026 22:23:37
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.43 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#include <algorithm>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int node_count, edge_count;
vector<vector<int>> graph;
vector<int> discovery_time, lowest_time;
stack<pair<int, int>> active_edges;
vector<vector<int>> components;
int timer = 0;

void dfs(int current_node, int parent_node = -1) {
    discovery_time[current_node] = lowest_time[current_node] = ++timer;

    for (int next_node : graph[current_node]) {
        if (next_node == parent_node) {
            continue;
        }

        if (discovery_time[next_node] != 0) {
            lowest_time[current_node] = min(lowest_time[current_node], discovery_time[next_node]);
            if (discovery_time[next_node] < discovery_time[current_node]) {
                active_edges.push({current_node, next_node});
            }
        } else {
            active_edges.push({current_node, next_node});
            dfs(next_node, current_node);

            lowest_time[current_node] = min(lowest_time[current_node], lowest_time[next_node]);

            if (lowest_time[next_node] >= discovery_time[current_node]) {
                set<int> unique_nodes;
                while (true) {
                    pair<int, int> edge = active_edges.top();
                    active_edges.pop();

                    unique_nodes.insert(edge.first);
                    unique_nodes.insert(edge.second);

                    if (edge == make_pair(current_node, next_node)) {
                        break;
                    }
                }
                components.push_back(vector<int>(unique_nodes.begin(), unique_nodes.end()));
            }
        }
    }
}

int main() {
    fin >> node_count >> edge_count;

    graph.assign(node_count + 1, vector<int>());
    discovery_time.assign(node_count + 1, 0);
    lowest_time.assign(node_count + 1, 0);

    for (int i = 0; i < edge_count; ++i) {
        int first_node, second_node;
        fin >> first_node >> second_node;
        graph[first_node].push_back(second_node);
        graph[second_node].push_back(first_node);
    }

    for (int node = 1; node <= node_count; ++node) {
        if (discovery_time[node] == 0) {
            dfs(node);
        }
    }

    fout << components.size() << "\n";
    for (const auto& comp : components) {
        for (int node : comp) {
            fout << node << " ";
        }
        fout << "\n";
    }

    return 0;
}