Cod sursa(job #1379092)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 6 martie 2015 16:15:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 100000 + 1;
const int Mmax = 200000 + 1;

pair<int,int> stiva[Mmax];
vector<int> G[Nmax];
vector<int> BC[Nmax];
int lowIndex[Nmax], Index[Nmax];

int N, M, nrComp, top;

void biconex(int x, int y)
{
    pair<int,int> E;
    nrComp++;

    do
    {
        E = stiva[top--];
        BC[nrComp].push_back(E.first);
        BC[nrComp].push_back(E.second);

    } while ( E.first != x || E.second != y );
}

void dfs(int nod, int dad, int d)
{
    lowIndex[nod] = Index[nod] = d;

    for (int son: G[nod])
        if ( son != dad )
        {
            if ( Index[son] == 0 )
            {
                stiva[ ++top ] = {nod, son};
                dfs(son, nod, d + 1);
                lowIndex[nod] = min(lowIndex[nod], lowIndex[son]);

                if ( lowIndex[son] >= Index[nod] )
                    biconex(nod, son);
            }
            else
                lowIndex[nod] = min(lowIndex[nod], Index[son]);
        }
}

void printBC()
{
    ofstream out("biconex.out");

    out << nrComp << "\n";

    for ( int i = 1; i <= nrComp; ++i )
    {
        sort(BC[i].begin(), BC[i].end());
        BC[i].erase(unique(BC[i].begin(), BC[i].end()), BC[i].end());

        for (int x: BC[i])
            out << x << " ";

        out << "\n";
    }

    out.close();
}

int main()
{
    ifstream in("biconex.in");

    ios_base::sync_with_stdio(false);

    in >> N >> M;

    for ( int i = 1; i <= M; ++i )
    {
        int a, b;
        in >> a >> b;

        G[a].push_back(b);
        G[b].push_back(a);
    }

    dfs(1, 0, 1);
    printBC();

    return 0;
}