Cod sursa(job #2567177)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 3 martie 2020 15:39:38
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int


using namespace std;

vector <vector <int>> g, comps;
vector <int> low, lvl;
stack <int> stk;

void dfs(int nod, int par) {
    lvl[nod] = lvl[par] + 1;
    low[nod] = lvl[nod];
    stk.push(nod);
    for(auto it : g[nod]) {
        if(lvl[it] == 0) {
            dfs(it, nod);
            if(low[it] >= lvl[nod]) {
                comps.push_back(vector <int>());
                while(stk.top() != it) {
                    comps.back().push_back(stk.top());
                    stk.pop();
                }
                stk.pop();
                comps.back().push_back(it);
                comps.back().push_back(nod);
            }
            low[nod] = min(low[nod], low[it]);
        }
        else if(it != par) {
            low[nod] = min(low[nod], lvl[it]);
        }
    }
}

int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    int i, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    g.resize(n + 1);
    for(i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    low.resize(n + 1), lvl.resize(n + 1);
    for(i = 1; i <= n; i++) {
        if(lvl[i] == 0) {
            dfs(i, 0);
        }
    }
    cout << comps.size() << "\n";
    for(auto &arr : comps) {
        for(auto it : arr) {
            cout << it << " ";
        }
        cout << "\n";
    }

    return 0;
}