Cod sursa(job #1371132)

Utilizator tudorv96Tudor Varan tudorv96 Data 3 martie 2015 19:21:30
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

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

const int N = 1e5 + 5;

vector <int> g[N];
vector <pair <int, int> > st;
set <int> comp[N];
int n, m, c, lo[N], niv[N];

void remove(int x, int y) {
    pair <int, int> crt;
    do {
        crt = st.back();
        st.pop_back();
        comp[c].insert(crt.first);
        comp[c].insert(crt.second);
    } while (crt.first != x || crt.second != y);
    c++;
}

void dfs(int x, int tata, int l) {
    //cout << x << "\n" << flush;
    lo[x] = niv[x] = l;
    for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it) {
        if (*it == tata)
            continue;
        if (!niv[*it]) {
            st.push_back(make_pair (x, *it));
            dfs(*it, x, l + 1);
            lo[x] = min(lo[x], lo[*it]);
            if (lo[*it] >= niv[x])
                remove(x, *it);
        }
        else
            lo[x] = min(lo[x], niv[*it]);
    }
}

int main() {
    fin >> n >> m;
    for (int x, y, i = 0; i < m; ++i) {
        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";
    }
}