Cod sursa(job #1365758)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 28 februarie 2015 15:03:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

fstream f("biconex.in", ios::in);
fstream g("biconex.out", ios::out);

const int nmax = 100010;

vector <int> a[nmax], bicon[nmax];
stack <int> s;

int n, m, i, x, y, viz[nmax], low[nmax], niv[nmax], nrb;

void citire()
{
    f >> n >> m;
    for (i = 1; i <= m; i++)
    {
        f >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
}

void DFS(int nc, int lvl)
{
    viz[nc] = 1;
    low[nc] = lvl;
    niv[nc] = lvl;
    s.push(nc);
    for (vector <int>::iterator it = a[nc].begin(); it != a[nc].end(); ++it)
    {
        if (viz[*it])
        {
            if (niv[*it] < low[nc]) low[nc] = niv[*it];
        }
        else
        {
            DFS(*it, lvl + 1);
            if (low[*it] < low[nc]) low[nc] = low[*it];
            if (niv[nc] <= low[*it])
            {
                nrb++;
                do
                {
                    x = s.top();
                    s.pop();
                    bicon[nrb].push_back(x);
                } while (x != *it);
                bicon[nrb].push_back(nc);
            }
        }
    }
}

int main()
{
    citire();
    DFS(1, 0);
    g << nrb << "\n";
    for (i = 1; i <= nrb; i++)
    {
        for (vector <int>::iterator it = bicon[i].begin(); it != bicon[i].end(); ++it) g << *it << " ";
        g << "\n";
    }
    return 0;
}