Cod sursa(job #3283803)

Utilizator db_123Balaban David db_123 Data 10 martie 2025 15:36:36
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

struct Info {
    int node;
    int nxt;
    Info() = default;
    Info(int node, int nxt) : node(node), nxt(nxt) {}
};

int n, m;
vector<vector<int>> graph, biconex;

void read() {
    cin >> n >> m;
    graph.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }
}

void dfs(int node, int par, int &time, vector<int> &low, vector<int> &disc, vector<int> &curr_stk) {
    disc[node] = ++ time;
    low[node] = time;
    curr_stk.emplace_back(node);

    for (auto it : graph[node]) {
        if (it == par) {
            continue;
        }
        if (disc[it] == -1) {
            dfs(it, node, time, low, disc, curr_stk);
            low[node] = min(low[node], low[it]);

            if (low[it] >= disc[node]) {
                vector<int> temp;
                while (!curr_stk.empty() && curr_stk.back() != node) {
                    temp.emplace_back(curr_stk.back());
                    curr_stk.pop_back();
                }
                temp.emplace_back(node);
                if (temp.empty()) {
                    return;
                }
                biconex.emplace_back(temp);
            }
        }
        else {
            low[node] = min(low[node], low[it]);
        }
    }

}

void solve() {
    vector<int> low(n + 1, -1), disc(n + 1, -1), curr_stk;
    vector<bool> fr_stk(n + 1);
    int time = 0;
    for (int i = 1; i <= n; i++) {
        if (disc[i] != -1) {
            continue;
        }
        dfs(i, 0, time, low, disc, curr_stk);
    }

    cout << biconex.size() << "\n";

    for (auto it1 : biconex) {
        for (auto it2 : it1) {
            cout << it2 << " ";
        }
        cout << "\n";
    }
}

int main()
{

    read();
    solve();
    return 0;
}