Mai intai trebuie sa te autentifici.

Cod sursa(job #1541531)

Utilizator robx12lnLinca Robert robx12ln Data 4 decembrie 2015 10:41:23
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include<fstream>
#include<deque>
#include<vector>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int nivel[100005],Low[100005],f[100005],componente,n,m,x,y;
deque< pair<int,int> > d;
vector<int> v[100005],sol[100005];
void dfs( int nod, int niv, int tata){
    nivel[nod] = niv;
    Low[nod] = niv;
    f[nod] = 1;
    for( int i = 0; i < v[nod].size(); i++ ){
        int vecin = v[nod][i];
        if( tata == vecin )
            continue;
        if( f[vecin] == 0 ){
            d.push_back( make_pair( nod, vecin ) );
            dfs( vecin, niv + 1, nod );
            Low[nod] = min ( Low[nod], Low[vecin] );
            if( nivel[nod] <= Low[vecin] ){
                componente++;
                int nod1 = d.back().first;
                int nod2 = d.back().second;
                while( nod1 != nod && nod2 != vecin  && !d.empty() ){
                    sol[componente].push_back(nod2);
                    d.pop_back();
                    nod1 = d.back().first;
                    nod2 = d.back().second;
                }
                sol[componente].push_back(nod2);
                sol[componente].push_back(nod1);
                d.pop_back();
            }
        }else{
            Low[nod] = min( Low[nod], nivel[vecin] );
        }
    }
}
int main(){
    cin >> n >> m;
    for( int  i = 1; i <= m; i++ ){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,1,0);
    cout << componente << "\n";
    for( int i = 1; i <= componente; i ++ ){
        for( int j = 0; j < sol[i].size(); j ++ ){
            cout << sol[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}