Cod sursa(job #1413277)

Utilizator Ionut228Ionut Calofir Ionut228 Data 1 aprilie 2015 19:32:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int N, M, nrsol;
int nodLvl[100005], nodInt[100005];
vector<int> V[100005], sol[100005];
stack<pair<int, int> > ST;
bool used[100005];

void make_sol(int nod, int fiu)
{
    while (!ST.empty() && (ST.top().first != nod || ST.top().second != fiu))
    {
        sol[nrsol].push_back(ST.top().second);
        ST.pop();
    }
    ST.pop();
    sol[nrsol].push_back(fiu);
    sol[nrsol].push_back(nod);
}

void dfs(int nod, int TT, int lvl)
{
    nodLvl[nod] = lvl;

    for (vector<int>::iterator it = V[nod].begin(); it != V[nod].end(); ++it)
    {
        int vecin = *it;
        if (*it == TT)
            continue;
        if (!used[*it])
        {
            used[*it] = true;
            ST.push(make_pair(nod, *it));
            dfs(*it, nod, lvl + 1);

            if (nodLvl[nodInt[nod]] > nodLvl[nodInt[*it]])
                nodInt[nod] = nodInt[*it];

            if (nodLvl[nodInt[*it]] >= lvl)
            {
                ++nrsol;
                make_sol(nod, *it);
            }
        }
        else if (used[*it])
        {
            if (nodLvl[nodInt[nod]] > nodLvl[nodInt[*it]])
                nodInt[nod] = nodInt[*it];
        }
    }
}

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

    for (int i = 1; i <= N; ++i)
        nodInt[i] = i;
    used[1] = true;
    dfs(1, 1, 1);

    fout << nrsol << '\n';
    for (int i = 1; i <= nrsol; ++i)
    {
        for (vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
            fout << *it << ' ';
        fout << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}