Cod sursa(job #1368354)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 2 martie 2015 16:29:11
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include <algorithm>
#include <fstream>
#include <stack>
#include <vector>

#define N 100001
#define M 200001
using namespace std;

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

struct muchie
{
    int x, y;
};

int vf[2 * M], urm[2 * M], lst[N], nr = 0;

int n, m;
int t[N], l[N], niv[N];
bool ok[N];

vector<int> componente[N];
stack<muchie> s;

int nrc = 0;

void df(int x)
{
    ok[x] = 1;
    l[x] = niv[x];

    for(int p = lst[x]; p; p = urm[p])
    {
        int y = vf[p];

        if(!ok[y])
        {
            s.push((muchie){x, y});
            t[y] = x;
            niv[y] = niv[x] + 1;
            df(y);

            if(l[y] < l[x])
                l[x] = l[y];
            if(l[y] >= niv[x])
            {
                //pct de articulatie
                nrc++;
                int x1, y1;
                do
                {
                    muchie m = s.top();
                    s.pop();
                    x1 = m.x;
                    y1 = m.y;
                    componente[nrc].push_back(x1);
                    componente[nrc].push_back(y1);
                }while(x1 != x && y1 != y);
            }
        }
        else if(y != t[x] && niv[y] < l[x])
        {
            //muchie de intoarcere
            l[x] = niv[y];
        }
    }
}

void adauga_muchie(int x, int y)
{
    vf[++nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
    vf[++nr] = x;
    urm[nr] = lst[y];
    lst[y] = nr;
}

void citire()
{
    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;
        adauga_muchie(x, y);
    }
}

void afisare()
{
    out << nrc << '\n';

    for(int i = 1; i <= nrc; i++)
    {
        sort(componente[i].begin(), componente[i].end());
        componente[i].erase(unique(componente[i].begin(), componente[i].end()), componente[i].end());
        for(size_t j = 0; j < componente[i].size(); j++)
            out << componente[i][j] << ' ';
        out << '\n';
    }
}

int main()
{
    citire();

    for(int i = 1; i <= n; i++)
        if(!ok[i])
            df(i);

    afisare();
    return 0;
}