Cod sursa(job #2203545)

Utilizator Menage_a_011UPB Cheseli Neatu Popescu Menage_a_011 Data 12 mai 2018 17:20:00
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.29 kb
// https://goo.gl/fBmFxu
#include <bits/stdc++.h>
using namespace std;

#define NMAX        100009
#define MMAX        200009
#define kInf        (1 << 30)
#define kInfLL      (1LL << 60)
#define kMod        666013
#define edge pair<int, int>
#define x first
#define y second

// number of tests from "in"
int test_cnt = 1;
void clean_test();

// your global variables are here
int n, m;
vector<int> G[NMAX];
int T[NMAX];

vector<int> cv;
vector<edge> ce;

stack<edge> st;
vector<vector<int> > all_bcc;


int current_start;
int found[NMAX], low_link[NMAX];


template<typename T>
void make_unique(vector<T> &v) {
    sort(v.begin(), v.end());
    auto it = unique(v.begin(), v.end());
    v.erase(it, v.end());
}

void get_bcc(edge target) {
    vector<int> bcc;
    edge e;

    do {
        e = st.top();
        st.pop();

        bcc.push_back(e.first);
        bcc.push_back(e.second);
    } while (e != target);


    make_unique(bcc);
    all_bcc.push_back(bcc);
}

void dfs(int node) {
    int children = 0;
    found[node] = low_link[node] = ++current_start;

    for (auto &x : G[node]) {
        if (!T[x]) {
            ++children;
            T[x] = node;

            st.push({node, x});
            dfs(x);

            low_link[node] = min(low_link[node], low_link[x]);

            // cut vertex
            if (T[node] != node && low_link[x] >= found[node]) {
                cv.push_back(node);
            }

            // critical edge
            if (low_link[x] > found[node]) {
                ce.push_back({node, x});
            }

            if (low_link[x] >= found[node]) {
                get_bcc({node, x});
            }
        } else {
            if (T[x] != node) {
                low_link[node] = min(low_link[node], found[x]);
            }
        }
    }

    if (T[node] == node && children > 1) {
        cv.push_back(node);
    }
}

void tarjan() {
    for (int i = 1; i <= n; ++i) {
        if (!T[i]) {
            T[i] = i;
            dfs(i);
        }
    }

    make_unique(cv);
    make_unique(ce);
}

// your solution is here
void solve() {
    cin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    tarjan();

    cout << all_bcc.size() << "\n";
    for (auto &bcc : all_bcc) {
        for (auto &x : bcc) {
            cout << x << " ";
        }
        cout << "\n";
    }

    if (test_cnt > 0) {
        clean_test();
    }
}


void clean_test() {
    // clean if needed
    memset(T, 0, sizeof(T));

    cv.clear();
    ce.clear();
    all_bcc.clear();

    for (int i = 1; i <= n; ++i) {
        if (G[i].size())  {
            G[i].clear();
        }
    }

    // clean every shit
    n = m  = 0;
}

int main() {
    // din cauza ca fac redirectari, salvez starea lui cin si cout
    auto cin_buff = cin.rdbuf();
    auto cout_buff = cout.rdbuf();

    // las liniile urmatoare daca citesc din fisier
    ifstream fin("biconex.in");
    cin.rdbuf(fin.rdbuf()); // save and redirect

    // las liniile urmatoare daca afisez in fisier
    ofstream fout("biconex.out");
    cout.rdbuf(fout.rdbuf()); // save and redirect


//     cin >> test_cnt;
    while (test_cnt--) {
        solve();
    }

    // restore pentru cin si cout
    cin.rdbuf(cin_buff);
    cout.rdbuf(cout_buff);

    return 0;
}