Cod sursa(job #2430290)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 13 iunie 2019 20:13:15
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;
const int MAX_N = 1e5;

#define pb push_back

int timp;
bool viz[1 + MAX_N];
vector <int> gr[1 + MAX_N];
int up[1 + MAX_N], dn[1 + MAX_N];
vector <int> comp[1 + MAX_N];
stack <int> stk;
int nrbic;

void dfs (int node, int father) {
    viz[node] = true;
    up[node] = dn[node] = ++timp;
    stk.push (node);
    for (int &son : gr[node])
        if (son != father) {
            if (viz[son])
                dn[node] = min (dn[node], up[son]);
            else {
                dfs (son, node);
                dn[node] = min (dn[node], dn[son]);
                if (dn[son] >= up[node]) {
                    nrbic++;
                    while (!stk.empty () && stk.top () != son) {
                        comp[nrbic].pb (stk.top ());
                        stk.pop ();
                    }
                    comp[nrbic].pb (son); comp[nrbic].pb (node);
                    stk.pop ();
                }
            }
        }
}

int main() {
    freopen ("biconex.in", "r", stdin);
    freopen ("biconex.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        gr[x].pb (y);
        gr[y].pb (x);
    }
    timp = 0;
    dfs (1, 0);
    cout << nrbic << "\n";
    for (int i = 1; i <= nrbic; i++) {
        for (int &x : comp[i])
            cout << x << " ";
        cout << "\n";
    }
    return 0;
}