Cod sursa(job #2665262)

Utilizator FLORENTIN-GIULIANO.DUMITRUDumitru Florentin Giuliano FLORENTIN-GIULIANO.DUMITRU Data 30 octombrie 2020 14:29:27
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <fstream>

#include <iostream>

#include <set>

#include <stack>

#include <vector>

#include <algorithm>



using namespace std;



const char iname[] = "biconex.in";

const char oname[] = "biconex.out";



#define MAXN  100005

#define Min(a, b)  ((a) < (b) ? (a) : (b))



vector <int> adj[MAXN], dfn, low;



vector <vector <int> > C;



stack <pair <int, int> > stk;



void read_in(vector <int>* adj, int &n)

{

    ifstream in(iname);

    int cnt_edges, x, y;



    in >> n >> cnt_edges;

    for (; cnt_edges > 0; -- cnt_edges) {

        in >> x >> y;

        adj[x].push_back(y);

        adj[y].push_back(x);

    }

    in.close();

}



void cache_bc(const int x, const int y)

{

    vector <int> con; int tx, ty;

    do {

        tx = stk.top().first, ty = stk.top().second;

        stk.pop();

        con.push_back(tx), con.push_back(ty);

    }

    while (tx != x || ty != y);

    C.push_back(con);

}



void DF(const int n, const int fn, int number)

{

    vector <int>::iterator it;



    dfn[n] = low[n] = number;

    for (it = adj[n].begin(); it != adj[n].end(); ++ it) {

        if (*it == fn)   continue ;

        if (dfn[*it] == -1) {

            stk.push( make_pair(n, *it) );

            DF(*it, n, number + 1);

            low[n] = Min(low[n], low[*it]);

            if (low[*it] >= dfn[n])

                cache_bc(n, *it);

        }

        else

            low[n] = Min(low[n], dfn[*it]);

    }

}



int main(void)

{

    int n;

    read_in(adj, n);

    dfn.resize(n + 1), dfn.assign(n + 1, -1);

    low.resize(n + 1);

    DF(1, 0, 0);



    ofstream out(oname);

    out << C.size() << "\n";

    for (size_t i = 0; i < C.size(); ++ i) {

        sort(C[i].begin(), C[i].end());

        C[i].erase(unique(C[i].begin(), C[i].end()), C[i].end());

        for (size_t j = 0; j < C[i].size(); ++ j)

            out << C[i][j] << " ";

        out << "\n";

    }

    out.close();



    return 0;

}