Cod sursa(job #1825249)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 8 decembrie 2016 21:34:23
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cassert>

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];

graf g[nmax + 1];

vector< vector< int > > sol;

void dfs1 (int nod, int tata) {
    cat_de_sus[ nod ] = inf;
    d[ nod ] = inf;
    viz[ nod ] = 1;
    //fout << nod << "\n";
    for (auto i : g[ nod ]) {
        if (i != tata) {
            if (viz[ i ] == 0) {
                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 ]);
            }
        }
    }
    d[ nod ] = min(d[ nod ], cat_de_sus[ nod ]);
}

void dfs2 (int nod, int ind) {
    //assert(0 <= ind && ind < (int)sol.size());
    sol[ ind ].push_back( nod );
    viz[ nod ] = 1;
    //fout << nod << "\n";

    /*if (ind == 125000) {
        exit(0);
    }*/
    //assert(1 <= nod && nod <= 99996);

    for (auto i : g[ nod ]) {
        if (viz[ i ] == 0) {
            if (d[ i ] >= h[ nod ]) {
                sol.push_back(vector< int > (1, nod));
                dfs2(i, (int)sol.size() - 1);
            } else {
                dfs2(i, ind);
            }
        }
    }
}

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);

    memset(viz, 0, sizeof(viz));
    sol.push_back(vector< int > ());
    dfs2(1, 0);

    if (sol.size() > 0 && sol[ 0 ].size() == 1) {
        swap(sol[ 0 ], sol.back());
        sol.pop_back();
    }

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

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