Cod sursa(job #1822793)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 5 decembrie 2016 16:25:06
Problema Componente biconexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.21 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], comp[nmax + 1];
bool super_critic[nmax + 1];

int nrc;

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;

    int cate_sus = 0;
    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 ]);
            } else {
                cat_de_sus[ nod ] = min(cat_de_sus[ nod ], h[ i ]);
            }
        }

        cate_sus += (h[ i ] < h[ nod ]);
    }

    if (d[ nod ] >= h[ nod ] && cate_sus <= 1) {
        super_critic[ nod ] = 1;
    }

    d[ nod ] = min(d[ nod ], cat_de_sus[ nod ]);
}

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

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

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) {
            aux.clear();

            dfs2( i );
            ++ nrc;

            if (aux.size() > 1) {
                sol.push_back( aux );
            }
        }
    }

    for (int i = 1; i <= n; ++ i) {
        for (auto j : g[ i ]) {
            if (comp[ j ] != comp[ i ] && i < j) {
                aux.clear();
                aux.push_back( i ); aux.push_back( j );
                sol.push_back( aux );
            }
        }
    }

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

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