Cod sursa(job #1528375)

Utilizator HotSteelBeteag Ion Andrei HotSteel Data 19 noiembrie 2015 16:48:23
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <fstream>

#include <vector>
#include <stack>

#include <algorithm>

std::vector < std::vector < int > > adj_m;
std::vector < int > dis, low;
std::vector < std::vector < int > > comps;

std::stack < std::pair < int , int > > st;

void stack_it(int na, int nb)
{
    std::vector < int > comp;
    int x, y;

    do
    {
        x = st.top().first;
        y = st.top().second;

        st.pop();

        comp.push_back(x);
        comp.push_back(y);
    }while(x != na || y != nb);

    comps.push_back(comp);
}

void dfs(int node, int father, int time)
{
    dis [node] = low [node] = time;
    std::size_t i;
    for(i = 1 ; i < adj_m[node].size() ; ++i)
    {
        int cnode = adj_m[node][i];

        if(cnode == father)
            continue;

        if(dis[cnode] ==  -1)
        {
            st.push(std::make_pair(node, cnode));

            dfs(cnode, node, time + 1);

            low[node] = std::min(low[node], low[cnode]);

            if(low[cnode] >= dis[node])
            {
                stack_it(node, cnode);
            }
        }
        else
        {
            low[node] = std::min(low[node], dis[cnode]);
        }
    }
}

int main()
{
    std::ifstream fin("biconex.in");
    std::ofstream fout("biconex.out");

    int n, m;

    fin >> n;

    adj_m.assign(n + 1, std::vector < int >(1));
    dis.assign(n + 1, -1);
    low.assign(n + 1, 0);

    fin >> m;

    int c;
    int na, nb;
    for(c = 1 ; c <= m ; ++c)
    {
        fin >> na >> nb;

        adj_m[na].push_back(nb);
        adj_m[nb].push_back(na);
    }

    dfs(1, 0, 1);

    fout << comps.size() << "\n";

    std::size_t i, j;
    for(i = 0 ; i < comps.size(); ++i)
    {
        std::sort(comps[i].begin(), comps[i].end());

        comps[i].erase(std::unique(comps[i].begin(), comps[i].end()), comps[i].end());

        for(j = 0 ; j < comps[i].size() ; ++j)
        {
            fout << comps[i][j] << " ";
        }

        fout << "\n";
    }

    return 0;
}