Cod sursa(job #2698879)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 23 ianuarie 2021 11:02:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5;
vector <int> G[Nmax];

int low[Nmax];
int lvl[Nmax];

stack < pair <int, int> > stk;
vector < vector <int> > bic_comp;

void get_comp(pair <int, int> stop_edge) {
    vector <int> aux;

    while (true) {
        pair <int, int> tp = stk.top();
        stk.pop();

        aux.push_back(tp.first);
        aux.push_back(tp.second);

        if (tp == stop_edge) 
            break;
    }

    sort(aux.begin(), aux.end());
    aux.erase(unique(aux.begin(), aux.end()), aux.end());
    bic_comp.push_back(aux);
}

void DFS(int node = 1, int parent = 0) {
    lvl[node] = low[node] = lvl[parent] + 1;

    for (int nei : G[node]) {
        if (nei == parent) 
            continue;

        if (!lvl[nei]) {
            stk.push({node, nei});
            DFS(nei, node);
            low[node] = min(low[nei], low[node]);

            if (low[nei] >= lvl[node]) // node punct critic
                get_comp({node, nei});
        }
        else 
            low[node] = min(low[node], lvl[nei]);
    }
}

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

    int n, m;
    cin >> n >> m;

    while (m--) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    DFS();

    cout << bic_comp.size() << '\n';
    for (auto & line : bic_comp) {
        for (int x : line)
            cout << x << ' ';
        cout << '\n';
    }

    return 0;
}