Cod sursa(job #2470493)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 9 octombrie 2019 12:11:17
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <bits/stdc++.h>
#define N_MAX 100000
using namespace std;


bool visited[N_MAX + 1];

size_t visitedNodeTime[N_MAX + 1];

size_t lowestReachableNodeTime[N_MAX + 1];

stack<size_t> nodesStack;

size_t TIME = 1;

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

vector<vector<size_t>> biconnectedComponents;


void biconnected_components(size_t node, size_t parent)
{
    visited[node] = true;
    visitedNodeTime[node] = TIME;
    lowestReachableNodeTime[node] = TIME;

    ++TIME;

    nodesStack.push(node);

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

        if(!visited[neighbour])
        {
            biconnected_components(neighbour, node);

            lowestReachableNodeTime[node] = min(lowestReachableNodeTime[node], lowestReachableNodeTime[neighbour]);

            if(visitedNodeTime[node] <= lowestReachableNodeTime[neighbour])
        {
            vector<size_t> biconnectedComponent;

            nodesStack.push(node);

            do {
                biconnectedComponent.push_back(nodesStack.top());
                nodesStack.pop();
            } while(nodesStack.top() != node);

            biconnectedComponents.push_back(biconnectedComponent);
        }
        }
        else lowestReachableNodeTime[node] = min(lowestReachableNodeTime[node], visitedNodeTime[neighbour]);



    }


    return;
}

int main()
{
    size_t N, M, x, y;

    ifstream fin("biconex.in");
    ofstream fout("biconex.out");

    fin >> N >> M;

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

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

    for(size_t i = 1; i <= N; ++i)
    {
        if(!visited[i]) biconnected_components(i, 0);
    }

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

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

    return 0;
}