Cod sursa(job #3003213)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 15 martie 2023 16:34:11
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>

#define DIM 100005

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n, m;
int lvl[DIM], minLvl[DIM];
vector<int> edges[DIM];
bitset<DIM> v;
stack<pair<int, int>> s;
int ansNr;
vector<int> ans[DIM];

void dfs(int node) {
    v[node] = true;
    minLvl[node] = lvl[node];
    for (auto child: edges[node]) {
        if (!v[child]) {
            lvl[child] = lvl[node] + 1;
            s.push({node, child});
            dfs(child);
            if (minLvl[child] >= lvl[node]) {
                ansNr++;
                while (s.top().first != node || s.top().second != child) {
                    ans[ansNr].push_back(s.top().second);
                    s.pop();
                }
                ans[ansNr].push_back(node);
                ans[ansNr].push_back(child);
                s.pop();
            }

            minLvl[node] = min(minLvl[node], minLvl[child]);
        } else {
            minLvl[node] = min(lvl[child], minLvl[node]);
        }
    }
}

int main() {

    f >> n >> m;

    for (int i = 1; i <= m; i++) {
        int x, y;
        f >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    dfs(1);

    g << ansNr << "\n";
    for (int i = 1; i <= ansNr; i++, g << "\n") {
        for (auto x: ans[i]) {
            g << x << " ";
        }
    }

    return 0;
}