Cod sursa(job #3210015)

Utilizator PetraPetra Hedesiu Petra Data 4 martie 2024 12:49:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <bits/stdc++.h>

#define NMAX 100002

using namespace std;

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

int n, m, level[NMAX], minlevel[NMAX], root = 1;
vector<int> G[NMAX];
bitset<NMAX> viz;
stack<pair<int, int>> edges;
vector<unordered_set<int>> biconnected_components;

void read_data()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        fin >>  x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void extract_biconected_components(int nod, int vec)
{
    unordered_set<int> bc;
    pair<int, int> edge;

    do {
        edge = edges.top();
        edges.pop();

        bc.insert(edge.first);
        bc.insert(edge.second);
    }
    while(edge.first != nod && edge.second != vec);

    biconnected_components.push_back(bc);
}

void dfs(int nod, int dad)
{
    viz[nod] = true;
    level[nod] = level[dad] + 1;
    minlevel[nod] = level[dad] + 1;

    for (auto vec : G[nod])
    {
        if (vec == dad) continue;

        if (viz[vec] == true)
        {
            // back edge
            minlevel[nod] = min(minlevel[nod], level[vec]);
        }
        else
        {
            // tree edge

            edges.push(make_pair(nod, vec));
            dfs(vec, nod);
            minlevel[nod] = min(minlevel[nod], minlevel[vec]);

            if (minlevel[vec] >= level[nod])
                extract_biconected_components(nod, vec);
        }
    }
}

void print()
{
    fout << biconnected_components.size() << "\n";
    for (auto bc : biconnected_components)
    {
        for (auto nod : bc)
            fout << nod << " ";
        fout << "\n";
    }
    fout << "\n";
}

int main()
{
    read_data();

    dfs(root, 0);

    print();
    return 0;
}