Cod sursa(job #2176006)

Utilizator felixiPuscasu Felix felixi Data 16 martie 2018 20:22:51
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
#include<bits/stdc++.h>

using namespace std;

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

const int NMAX = 100000;

struct Biconexe
{
    /// takes an undirected graph (with both (x,y) (y,x) edges included)
    /// and returns a list of connected component an a per CRITICAL NODE basis

    static const int NMAX = NMAX;  /// copies constant from global scoe, just c++

    int N;
    stack<pair<int,int>> stk;
    vector<vector<int>> comps;
    vector<int> G[NMAX+2];
    bool viz[NMAX+2];
    int niv[NMAX+2], low[NMAX+2];

    Biconexe(int n, vector<int> (&g)[NMAX+2])
    {
        N = n;
        for( int i = 1;  i <= N;  ++i ) G[i] = g[i];
    }

    void another_component(int x, int y)
    {
        int lx, ly;
        vector<int> comp;

        do {
            lx = stk.top().first; ly = stk.top().second;
            comp.push_back(ly);
            stk.pop();
        } while( !(x == lx && y == ly) );
        comp.push_back(x);

        comps.push_back(comp);
    }

    void dfs(int nod, int tata = -1, int time = 1)
    {
        viz[nod] = 1;
        niv[nod] = low[nod] = time;
        for( int& x : G[nod] ) {
            if( !viz[x] ) {
                stk.push({nod, x});
                dfs(x, nod, time + 1);
                low[nod] = min(low[nod], low[x]);
                if( low[x] >= niv[nod] )
                    another_component(nod, x);
            }
            else {
                low[nod] = min(low[nod], niv[x]);
            }
        }
    }

    vector<vector<int>> getBiconexe()
    {
        memset(viz, 0, sizeof(viz));
        for( int i = 1;  i <= N;  ++i ) if( !viz[i] )
            dfs(i);
        return comps;
    }

};

int main()
{
    vector<int> G[NMAX+2];
    int N, M;
    in >> N >> M;
    for( int i = 1;  i <= M;  ++i ) {
        int x,y;
        in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    Biconexe CB(N, G);
    auto bicone = CB.getBiconexe();

   /// dfs2(2, -1);
    out << bicone.size()<< '\n';
    for( auto & ln : bicone )  {
       /// normalize(ln);
        for( const auto & x : ln ) out << x << ' ';
        out << '\n';
    }
    return 0;
}