Cod sursa(job #1521883)

Utilizator bogdanciurezubogdan ciurezu bogdanciurezu Data 10 noiembrie 2015 22:11:16
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int nmax = 100050;

vector <int> graf[nmax], componente[nmax];
int F[nmax], Stk[nmax], howHigh[nmax], lvl[nmax], nrComp, n, m;

void DFS(int poz){
    F[poz] = true;
    Stk[ ++Stk[0] ] = poz;
    howHigh[poz] = lvl[poz];

    for(auto node: graf[poz] ){
        if( !F[node] ){
            lvl[node] = lvl[poz] + 1;
            DFS(node);

            howHigh[poz] = min( howHigh[poz], howHigh[node] );

            if(howHigh[node] >= howHigh[poz]){
                while( Stk[ Stk[0] + 1 ] == node){
                    ++nrComp;
                    componente[ nrComp ].push_back( Stk[Stk[0]--] );
                }
                    componente[ nrComp ].push_back( poz );
            }
        }
        else if( howHigh[poz] > howHigh[node] )
            howHigh[poz] = howHigh[node];
    }
}

int main()
{
    f>>n>>m;
    g<<n<<' '<<m<<'\n';

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

        graf[x].push_back(y);
        graf[y].push_back(x);
    }



    for(int i = 1; i <= n; ++i){
        if( !F[i] ){
            DFS(1);
        }
    }

    g<<nrComp<<'\n';
    for(int i = 1; i <= nrComp; ++i){
        for(auto j : graf[i] )
            g<<j<<' ';
        g<<'\n';
    }
    return 0;
}