Cod sursa(job #2470532)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 9 octombrie 2019 13:26:42
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <fstream>
#include <vector>
#include <string>
#include <iostream>
#define N_MAX 100000 + 1

using namespace std;

size_t N, M;
vector<vector<size_t>> graph(N_MAX, vector<size_t>());

size_t nodeStack[N_MAX];
size_t stackSize = 0;

size_t _time = 1;
size_t nodeTime[N_MAX];
size_t lowestTime[N_MAX];

vector<vector<size_t>> biconnectedComponents;


vector<size_t> get_biconnected_component(size_t first, size_t last)
{
    vector<size_t> biconnectedComponent;

    while(nodeStack[stackSize] != last)
    {
        biconnectedComponent.push_back(nodeStack[stackSize]);
        --stackSize;
    }

    biconnectedComponent.push_back(last);
    biconnectedComponent.push_back(first);

    --stackSize;

    return biconnectedComponent;
}


void DFS(size_t node, size_t parent)
{
    nodeTime[node] = _time;
    lowestTime[node] = _time;
    ++_time;

    nodeStack[++stackSize] = node;


    for(auto& neightbour : graph[node])
    {
        if(neightbour == parent) continue;

        if(nodeTime[neightbour] == 0)
        {
            DFS(neightbour, node);

            lowestTime[node] = min(lowestTime[node], lowestTime[neightbour]);

            if(nodeTime[node] <= lowestTime[neightbour])
            {
                biconnectedComponents.push_back(get_biconnected_component(node, neightbour));
            }
        }
        else lowestTime[node] = min(lowestTime[node], nodeTime[neightbour]);
    }
}


void read_graph_from_file()
{
    ifstream fin("biconex.in");

    fin >> N >> M;

    size_t x, y;

    for(size_t i = 1; i <= M; ++i)
    {
        fin >> x >> y;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    return;
}


void print_biconnected_components_to_file()
{
    ofstream fout("biconex.out");

    fout << biconnectedComponents.size() << '\n';

    for(auto& biconnectedComponent : biconnectedComponents)
    {
        for(auto& node : biconnectedComponent) fout << node << ' ';
        fout << '\n';
    }

    return;
}

int main()
{
    read_graph_from_file();

    for(size_t i = 1; i <= N; ++i)
    {
        if(nodeTime[i] == 0) DFS(i, 0);
    }

    print_biconnected_components_to_file();
}