Cod sursa(job #1224093)

Utilizator EpictetStamatin Cristian Epictet Data 29 august 2014 17:26:46
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N, M, x, y;
vector < int > V[110];
vector < vector < int > > Sol;
stack < int > St;
bool fr[110];
int sol, dfn[110], low[110];

void Add_Comp_Biconex(int fnode, int node)
{
    vector < int > aux;

    while (St.top() != node)
    {
        aux.push_back(St.top());
        St.pop();
    }

    aux.push_back(node);
    St.pop();

    aux.push_back(fnode);

    Sol.push_back(aux);
}

int Biconex(int nod, int lvl)
{
    dfn[nod] = lvl;
    low[nod] = lvl;

    fr[nod] = 1;
    St.push(nod);

    for (int j=0; j<V[nod].size(); j++)
    {
        if (fr[V[nod][j]])
        {
            low[nod] = min(low[nod], dfn[V[nod][j]]);
        }
        else
        {
            Biconex(V[nod][j], lvl + 1);

            low[nod] = min(low[nod], low[V[nod][j]]);

            if (low[V[nod][j]] >= lvl) Add_Comp_Biconex(nod, V[nod][j]);
        }
    }
}

int main()
{
    fin >> N >> M;
    for (int i=1; i<=M; i++)
    {
        fin >> x >> y;
        V[x].push_back(y);
        V[y].push_back(x);
    }

    Biconex(1, 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;
}