Cod sursa(job #1821897)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 3 decembrie 2016 20:49:44
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include<fstream>
#include<vector>

using namespace std;

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

typedef vector< int > graf;

const int nmax = 1e5;
const int inf = (1 << 30) - 1 + (1 << 30);

bool viz[nmax + 1];
int h[nmax + 1], d[nmax + 1], cat_de_sus[nmax + 1];
bool super_critic[nmax + 1];

graf g[nmax + 1];

vector< int > aux;
vector< vector< int > > sol;

void dfs1 (int nod, int tata) {
    cat_de_sus[ nod ] = inf;
    d[ nod ] = inf;

    bool frunza = 1;
    for (auto i : g[ nod ]) {
        if (i != tata) {
            if (h[ i ] == inf) {
                h[ i ] = h[ nod ] + 1;
                dfs1(i, nod);

                d[ nod ] = min(d[ nod ], d[ i ]);
                frunza = 0;
            } else {
                cat_de_sus[ nod ] = min(cat_de_sus[ nod ], h[ i ]);
            }
        }
    }

    if (d[ nod ] >= h[ nod ] && frunza == 0) {
        super_critic[ nod ] = 1;
    }
    d[ nod ] = min(d[ nod ], cat_de_sus[ nod ]);
}

void dfs2 (int nod, int t) {
    aux.push_back( nod );
    viz[ nod ] = 1;

    if (super_critic[ nod ] == 0) {
        for (auto i : g[ nod ]) {
            if (viz[ i ] == 0) {
                dfs2(i, nod);
            }
        }
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        int x, y;
        fin >> x >> y;
        g[ x ].push_back( y );
        g[ y ].push_back( x );
    }
    for (int i = 1; i <= n; ++ i) {
        h[ i ] = inf;
    }
    h[ 1 ] = 0;

    dfs1(1, 0);

    for (int i = 1; i <= n; ++ i) {
        if (super_critic[ i ] == 1) {
            for (auto j : g[ i ]) {
                if (h[ j ] != h[ i ] + 1) continue;

                aux.clear();
                dfs2(j, 0);

                if (viz[ i ] == 0) {
                    aux.push_back( i );
                }
                sol.push_back( aux );

                for (auto k : aux) {
                    viz[ k ] = 0;
                }
            }
        }
    }

    fout << (int)sol.size() << "\n";
    for (auto it : sol) {
        for (auto it2 : it) {
            fout << it2 << " ";
        }
        fout << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}