Cod sursa(job #1900376)

Utilizator bt.panteaPantea Beniamin bt.pantea Data 3 martie 2017 12:39:18
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");

vector < set < int > > sol; // componentele biconexe
stack < pair < int, int > > stk; // stiva muchi
vector < int > a[NMAX];  // matricea de adiacenta
int low[NMAX], dfn[NMAX], n, m;

void BiconexComponent(int x, int y)
{
    set < int > aux;
    int a, b;
    do
    {
        a = stk.top().first;
        b = stk.top().second;
        stk.pop();
        //aux.push_back(a);
        //if (aux.find(a) == aux.end())
            aux.insert(a);
        //if (aux.find(b) == aux.end())
            aux.insert(b);
    } while (a != x || b != y);
    sol.push_back(aux);
}

void df(int nod, int precNod)
{
    low[nod] = dfn[nod] = dfn[precNod] + 1;
    for (unsigned i = 0; i < a[nod].size(); i++)
    {
        int next = a[nod][i];
        if (next == nod) continue;
        if (!dfn[next])
        {
            stk.push(make_pair(nod, next));
            df(next, nod);
            low[nod] = min(low[nod], low[next]);
            if (low[next] >= dfn[nod])
                BiconexComponent(nod, next);
        }
        else low[nod] = min(low[nod], dfn[next]);
    }
}
int main()
{
    f>>n>>m;
    while (m--)
    {
        int x, y;
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    df(1, 0);
    g<<sol.size()<<'\n';
    for (int i = 0; i < sol.size(); i++)
    {
        set < int >::iterator it;
        for (it = sol[i].begin(); it != sol[i].end(); it++)
            g<<* it<<' ';
        g<<'\n';
    }
    return 0;
}