Cod sursa(job #1521904)

Utilizator bogdanciurezubogdan ciurezu bogdanciurezu Data 10 noiembrie 2015 22:42:17
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 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(int node = 0; node < graf[poz].size(); ++node ){
        if( !F[ graf[poz][node] ] ){
            lvl[ graf[poz][node] ] = lvl[poz] + 1;
            DFS( graf[poz][node] );

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

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

int main()
{
    f>>n>>m;

    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(i);
        }
    }

    g<<nrComp<<'\n';
    for(int i = 1; i <= nrComp; ++i){
        for( int j = 0; j < componente[i].size(); ++j )
            g<< componente[i][j] <<' ';
        g<<'\n';
    }
    return 0;
}