Cod sursa(job #3376138)

Utilizator papergodChivu Razvan Gabriel papergod Data 16 noiembrie 2026 12:43:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.17 kb
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <stack>
#include <algorithm>
#include <fstream>
#include <set>

using namespace std;

struct Edge {
    int to;
    int cost;
};

struct Node {
    int n = -1;
    vector<Edge> Adj;

    bool IsAdjTo(int v) {
        for (auto& i : Adj) {
            if (i.to == v) {
                return true;
            }
        }
        return false;
    }
};

struct Graph {
private:
    bool Oriented;
    bool Weighted;
    vector<Node> Nodes;
    int edgeCount = 0;
public:
    Graph(bool _Oriented = true, bool _Weighted = false) {
        Oriented = _Oriented;
        Weighted = _Weighted;
    }

    void SetOriented(bool _Oriented) {
        Oriented = _Oriented;
    }

    void SetNodeCount(int n) {
        Nodes.resize(n);
        for (int i = 0; i < n; i++) {
            Nodes[i].n = i;
        }
    }

    int GetNodeCount() {
        return Nodes.size();
    }

    Node& operator[] (int i) {
        return Nodes[i];
    }

    void AddEdge(int u, int v, int w = 1) {
        Nodes[u].Adj.push_back({.to = v, .cost = w});
        if (!Oriented)
            Nodes[v].Adj.push_back({.to = u, .cost = w});
        edgeCount++;
    }

    vector<Edge>& GetEdges(int u) {
        return Nodes[u].Adj;
    }

    int GetEdgeCount() const {
        return edgeCount;
    }
};

#define in fin
#define out fout

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

void ReadMEdges(Graph &G, int M) {
    while (M--) {
        int u, v;
        in >> u >> v;
        G.AddEdge(u-1, v-1);
    }
}

void ReadGraph(Graph &G, int N, int M) {
    G.SetNodeCount(N);
    ReadMEdges(G, M);
}

void biconex_dfs(int u, int p, Graph& G, vector<int>& dfn, vector<int>& low, int& timer, stack<int>& st, vector<vector<int>>& bccs) {
    dfn[u] = low[u] = ++timer;
    st.push(u);

    for (auto& edge : G.GetEdges(u)) {
        int v = edge.to;
        if (v == p) continue;

        if (dfn[v]) {
            low[u] = min(low[u], dfn[v]);
        } else {
            biconex_dfs(v, u, G, dfn, low, timer, st, bccs);
            low[u] = min(low[u], low[v]);

            if (low[v] >= dfn[u]) {
                vector<int> current_bcc;
                current_bcc.push_back(u + 1);

                while (true) {
                    int node = st.top();
                    st.pop();
                    current_bcc.push_back(node + 1);
                    if (node == v) break;
                }
                bccs.push_back(current_bcc);
            }
        }
    }
}

void biconex() {
    int N, M;
    in >> N >> M;

    Graph G(false, false);
    G.SetNodeCount(N);

    for (int i = 0; i < M; ++i) {
        int u, v;
        in >> u >> v;
        G.AddEdge(u - 1, v - 1);
    }

    vector<int> dfn(N, 0);
    vector<int> low(N, 0);
    int timer = 0;
    stack<int> st;
    vector<vector<int>> bccs;

    for (int i = 0; i < N; ++i) {
        if (!dfn[i]) {
            biconex_dfs(i, -1, G, dfn, low, timer, st, bccs);
        }
    }

    out << bccs.size() << "\n";
    for (const auto& bcc : bccs) {
        for (int node : bcc) {
            out << node << " ";
        }
        out << "\n";
    }
}


int main() {
    biconex();
}