Cod sursa(job #2557828)

Utilizator KappaClausUrsu Ianis Vlad KappaClaus Data 26 februarie 2020 08:02:15
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <bits/stdc++.h>
using namespace std;

const int N_MAX = 1e5 + 1;

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

vector<int> DFS_ORDER(N_MAX, 0);
vector<int> LOW(N_MAX, 0);
stack<int> NODE_STACK;
vector<vector<int>> BICONNECTED_COMPONENTS;
int order_cnt = 0;

void dfsBiconnectedComponents(int node, int parent)
{
    DFS_ORDER[node] = LOW[node] = ++order_cnt;
    NODE_STACK.push(node);

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

        if(DFS_ORDER[next] != 0)
            LOW[node] = min(LOW[node], DFS_ORDER[next]);
        else
        {
            dfsBiconnectedComponents(next, node);

            LOW[node] = min(LOW[node], LOW[next]);

            if(DFS_ORDER[node] <= LOW[next])
            {
                vector<int> BICONNECTED_COMPONENT;

                int aux;

                do
                {
                    aux = NODE_STACK.top();
                    NODE_STACK.pop();

                    BICONNECTED_COMPONENT.push_back(aux);
                } while(aux != next);

                BICONNECTED_COMPONENT.push_back(node);

                BICONNECTED_COMPONENTS.push_back(BICONNECTED_COMPONENT);
            }
        }
    }
}

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

    fin >> N >> M;

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

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

    dfsBiconnectedComponents(1, -1);

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

    for(auto& BICONNECTED_COMPONENT : BICONNECTED_COMPONENTS)
    {
        for(auto& node : BICONNECTED_COMPONENT)
        {
            fout << node << ' ';
        }

        fout << '\n';
    }

}