Cod sursa(job #1412071)

Utilizator tudorv96Tudor Varan tudorv96 Data 1 aprilie 2015 09:09:59
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <vector>
#include <fstream>
#include <set>
#include <stack>
using namespace std;

ifstream fin ("biconex.in");
ofstream fout ("biconex.out");

const int N = 1e5 + 5;

set <int> comp[N];

vector <int> g[N];

stack <pair <int, int> > st;

int lo[N], niv[N], n, m, c;

void extract (int x, int y) {
    int crtx, crty;
    do {
        crtx = st.top().first;
        crty = st.top().second;
        st.pop();
        comp[c].insert(crtx);
        comp[c].insert(crty);
    } while (crtx != x || crty != y);
    ++c;
}

void dfs(int x, int tata, int lv) {
    lo[x] = niv[x] = lv;
    for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it) {
        if (*it == tata)
            continue;
        if (!niv[*it]) {
            st.push(make_pair (x, *it));
            dfs(*it, x, lv + 1);
            lo[x] = min(lo[x], lo[*it]);
            if (niv[x] <= lo[*it])
                extract(x, *it);
        }
        else
            lo[x] = min(lo[*it], niv[x]);
    }
}

int main() {
    fin >> n >> m;
    for (int x, y; m; --m) {
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, 0, 1);
    fout << c << "\n";
    for (int i = 0; i < c; ++i) {
        for (set <int> :: iterator it = comp[i].begin(); it != comp[i].end(); ++it)
            fout << *it << " ";
        fout << "\n";
    }
}