Cod sursa(job #3293863)

Utilizator db_123Balaban David db_123 Data 12 aprilie 2025 19:31:33
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

struct Info {
    int node1;
    int node2;
    Info() = default;
    Info(int node1, int node2) : node1(node1), node2(node2) {}
    bool operator==(Info a2) const {
        return node1 == a2.node1 && node2 == a2.node2;
    }
};

int n, m;
vector<vector<int>> graph, rs;
vector<int> disc, low;

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 &time, vector<Info> &stk) {
    disc[node] = ++time;
    low[node] = time;
    for (auto it : graph[node]) {
        if (disc[it] == -1) {
            stk.emplace_back(Info(node, it));
            dfs(it, time, stk);
            if (disc[node] <= low[it]) {
                set<int> st;
                while (!stk.empty() && !(stk.back() == Info(node, it))) {
                    st.insert(stk.back().node1);
                    st.insert(stk.back().node2);
                    stk.pop_back();
                }
                st.insert(node);
                st.insert(it);
                stk.pop_back();
                vector<int> temp;
                for (auto it : st) {
                    temp.emplace_back(it);
                }
                rs.emplace_back(temp);
            }
            low[node] = min(low[node], low[it]);
        }
        else {
            low[node] = min(low[node], disc[it]);
        }
    }
}

void solve() {
    disc.resize(n + 1, -1);
    low.resize(n + 1, -1);

    int time = 0;
    for (int i = 1; i <= n; i++) {
        if (disc[i] != -1) {
            continue;
        }
        vector<Info> temp;
        dfs(i, time, temp);
    }

    cout << rs.size() << "\n";
    for (auto it1 : rs) {
        for (auto it2 : it1) {
            cout << it2 << " ";
        }
        cout << "\n";
    }
}

int main() {

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