Cod sursa(job #1667524)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 28 martie 2016 23:24:46
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.35 kb
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

const int NMAX = 100005;

class BCCArticulationPoints {
    private:
        vector<int> st;

    public:
        int n, bcc;
        vector<int> low;
        vector<int> dft;
        vector<vector<int>> v;
        vector<vector<int>> comp;
        vector<bool> art;

        BCCArticulationPoints(int _n) {
            bcc = 0;
            n = _n;
            low.resize(_n + 5);
            dft.resize(_n + 5);
            v.resize(_n + 5);
            comp.resize(_n + 5);
            art.resize(_n + 5);
        }

        void add_edge(int x, int y) {
            v[x].pb(y);
            v[y].pb(x);
        }

        void find_BCC() {
            st.clear();
            dfs(1, 0);
        }

    private:
        void get_comp(int x, int y) {
            bcc++;
            while (st.back() != y) {
                comp[bcc].pb(st.back());
                st.pop_back();
            }
            comp[bcc].pb(y);
            st.pop_back();
            comp[bcc].pb(x);
        }
        void dfs(int x, int f) {
            dft[x] = low[x] = dft[f] + 1;

            for (auto it : v[x])
                if (it != f) {
                    if (!dft[it]) {
                        st.pb(it);
                        dfs(it, x);
                        low[x] = min(low[x], low[it]);

                        if (low[it] >= dft[x]) { // x is an articulation point
                            art[x] = 1;
                            get_comp(x, it);
                        }

                    } else {
                        low[x] = min(low[x], dft[it]);
                    }
                }
        }

};

BCCArticulationPoints g(NMAX);
int n, m;

int main() {
    cin.sync_with_stdio(false);

    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    scanf("%d%d", &n, &m);

    for (; m; m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        g.add_edge(x, y);
    }

    g.find_BCC();

    printf("%d\n", g.bcc);
    for (int i = 1; i <= g.bcc; i++) {
        for (auto it : g.comp[i])
            printf("%d ", it);
        printf("\n");
    }

    return 0;
}