Cod sursa(job #3004983)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 16 martie 2023 18:36:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int DIM = 100010;
int n, m, x, y;
int biconCompCnt = 0;
int level[DIM], low[DIM];
vector<int> l[DIM], biconComp[DIM];
stack<int> st;
bool visited[DIM];

void dfs(int node, int father, int lvl) {
    visited[node] = true;
    level[node] = low[node] = lvl;
    st.push(node);

    for (auto adjNode : l[node]) {
        if (adjNode == father) continue;

        if (!visited[adjNode]) {
            dfs(adjNode, node, lvl + 1);
            low[node] = min(low[node], low[adjNode]);

            if (level[node] <= low[adjNode]) {
                ++biconCompCnt;
                while (st.top() != adjNode) {
                    biconComp[biconCompCnt].push_back(st.top());
                    st.pop();
                }
                biconComp[biconCompCnt].push_back(adjNode);
                st.pop();
                biconComp[biconCompCnt].push_back(node);
            }
        } else {
            low[node] = min(low[node], level[adjNode]);
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y;
        l[x].push_back(y);
        l[y].push_back(x);
    }

    dfs(1, 0, 0);

    fout << biconCompCnt << '\n';
    for (int i = 1; i <= biconCompCnt; i++) {
        for (auto node : biconComp[i])
            fout << node << ' ';
        fout << '\n';
    }

    return 0;
}