Cod sursa(job #1167248)

Utilizator tudorv96Tudor Varan tudorv96 Data 4 aprilie 2014 17:55:48
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
#include <set>
#include <stack>
using namespace std;

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

const int N = 1e5 + 5;


int m, n, nr;
vector <int> g[N];
int niv[N], lo[N];
stack <pair <int, int> > s;
set <int> comp[N];

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

void dfs(int x, int tata, int level) {
    lo[x] = niv[x] = level;
    for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it) {
        if (*it == tata)
            continue;
        if (!niv[*it]) {
            s.push (make_pair (x, *it));
            dfs (*it, x, level + 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 << nr << "\n";
    for (int i = 0; i < nr; ++i) {
        for (set <int> :: iterator it = comp[i].begin(); it != comp[i].end(); ++it)
            fout << *it << " ";
        fout << "\n";
    }
}