Cod sursa(job #1165472)

Utilizator tudorv96Tudor Varan tudorv96 Data 2 aprilie 2014 18:37:39
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

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

const int N = 1e5 + 5;

int n, m, niv[N], nr;
vector <int> g[N], comp[N];
vector <bool> viz(N, 0);
stack <pair <int, int> > stiva;

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 (make_pair (x, *it));
            dfs (*it, x, level + 1);
            if (niv[*it] >= level) {
                pair <int, int> extract;
                do {
                    extract = stiva.top(); stiva.pop();
                    comp[nr].push_back (extract.first);
                    comp[nr].push_back (extract.second);

                } while (extract.first != x || extract.second != *it);
                nr++;
            }
        }
        if (*it != father)
            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 << nr << "\n";
    for (int i = 0; i < nr; ++i) {
        sort (comp[i].begin(), comp[i].end());
        for (vector <int> :: iterator it = comp[i].begin(); it != comp[i].end(); ++it)
            fout << *it << " ";
        fout << "\n";
    }
}