Cod sursa(job #1817606)

Utilizator zacuscaAlex Iordache zacusca Data 28 noiembrie 2016 09:38:49
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int N, M, V[100003];
vector < vector < int > > sol;
vector < int > G[100003], lev, minlev;
stack < pair < int, int > > S;

void create (int x, int y)
{
    vector < int > aux;
    aux.resize(0);
    int a, b;
    do
    {
        a = S.top().first;
        b = S.top().second;
        S.pop();
        aux.push_back(b);
    }
    while (a != x or b != y);
    aux.push_back(x);
    sol.push_back(aux);
}

void DFS (int node, int l)
{
    V[node] = 1;
    minlev[node] = lev[node] =  l;
    for (vector < int > :: iterator it = G[node].begin (), sf = G[node].end(); it != sf; ++ it)
    {
        if (!V[*it])
        {
            S.push (make_pair (node, *it));
            DFS (*it, 1 + l);
            minlev[node] = min(minlev[node], minlev[*it]);
            if (minlev[*it] >= lev[node])
                create (node, *it);
        }
        else minlev[node] = min(minlev[node], lev[*it]);
    }

}

int main ()
{
    fin >> N >> M;
    minlev.resize(N);
    lev.resize(N);
    for (int x, y, i = 1; i <= M; ++ i)
    {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for (int i = 1; i <= N; ++ i)
    {
        if (!V[i])
            DFS (i, 0);
    }

    fout << sol.size() << '\n';
    for (int i = 0; i < sol.size(); ++ i)
    {
        for (int j = 0; j < sol[i].size(); ++ j)
        {
            fout << sol[i][j] << ' ';
        }
        fout << '\n';
    }

    fout.close();
    return 0;
}