Cod sursa(job #1094750)

Utilizator tudorv96Tudor Varan tudorv96 Data 29 ianuarie 2014 19:56:50
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

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

const int N = 1e5 + 5;

vector <int> g[N], niv(N, 0);
vector <bool> viz(N, 0);
int n, m, k;
vector <pair <int, int> > stiva;
set <int> BC[N];

void dfs(int x, int father, int level) {
    viz[x] = 1;
    niv[x] = level;
    for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it) {
        if (!viz[*it]) {
            stiva.push_back (make_pair (x, *it));
            dfs (*it, x, level + 1);
            if (niv[*it] >= level) {
                pair <int, int> extract;
                do {
                    extract = stiva.back();
                    stiva.pop_back();
                    BC[k].insert (extract.first);
                    BC[k].insert (extract.second);
                } while (extract.first != x || extract.second != *it);
                k++;
            }
        }
        if (father != *it)
                niv[x] = min(niv[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 << k << "\n";
    for (int i = 0; i < k; ++i) {
        for (set <int> :: iterator it = BC[i].begin(); it != BC[i].end(); ++it)
            fout << *it << " ";
        fout << "\n";
    }
}