Cod sursa(job #1413475)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 1 aprilie 2015 21:41:17
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

const int NMAX = 100005;

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int N,M,x,y,nrsol;
int low[NMAX],lvl[NMAX];
vector <int> v[NMAX];
vector <int> sol[NMAX];
stack < pair<int,int> > S;
bool art[NMAX],viz[NMAX];

void afisare(int x, int y)
{
    int a,b;
    do
    {
        a = S.top().first;
        b = S.top().second;
        sol[nrsol].push_back(a);
        sol[nrsol].push_back(b);
        S.pop();
    } while(!(x == a && y == b));

    sort(sol[nrsol].begin(),sol[nrsol].end());
}

void DFS(int nod, int nivel, int parinte)
{
    lvl[nod] = low[nod] = nivel;

    for (int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        if (vecin == parinte)
            continue;

        if (!lvl[vecin])
        {
            S.push(make_pair(nod,vecin));
            DFS(vecin,nivel+1,nod);
            low[nod] = min(low[nod],low[vecin]);
            if (low[vecin] >= lvl[nod]) //nod buclucas
            {
                art[nod] = true;
                nrsol++;
                afisare(nod,vecin);
            }
        }
        else //muchie de intoarcere
        {
            low[nod] = min(low[nod],lvl[vecin]);
        }
    }
}

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

    DFS(1,1,0);

    g << nrsol << '\n';

    for (int i = 1; i <= nrsol; ++i)
    {
        g << sol[i][0] << " ";
        for (int j = 1; j < sol[i].size(); ++j)
        {
            if (sol[i][j] != sol[i][j-1])
            {
                g << sol[i][j] << " ";
            }
        }
        g << '\n';
    }
}