Cod sursa(job #3368162)

Utilizator ManelPuscas Darius Manel Data 13 octombrie 2026 12:36:19
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <stack>
using namespace std;
using VI = vector<int>;
using VB = vector<bool>;
using VVI = vector<VI>;
using PI = pair<int, int>;
using SI = set<int>;
using SS = set<SI>;

const int DIM = 1e5 + 23;

int n, m;
int ind;
VVI G;
VI t, low, index;
bool v[DIM];
stack<PI> stk;
SS cbc;
SI c;

void In();
void CompBiconexe();
void Tarjan(int x);
void ExtractCB();
void Out();

int main()
{
    In();
    CompBiconexe();
    Out();
}

void Out()
{
    cout << cbc.size() << '\n';
    for(auto comp : cbc)
    {
        for(auto node : comp)
            cout << node << ' ';
        cout << '\n';
    }
}

void ExtractCB(int x, int y)
{
    c.clear();
    while(!stk.empty())
    {
        auto [a, b] = stk.top();
        stk.pop();
        c.insert(a);
        c.insert(b);

        if(a == x && b == y)
            break;
    }
    cbc.insert(c);
}

void CompBiconexe()
{
    for(int node = 1; node <= n; ++node)
        if(!v[node])
            Tarjan(node);
}

void Tarjan(int x)
{
    v[x] = true;
    index[x] = low[x] = ++ind;

    for(auto y : G[x])
    {
        if(y == t[x])
            continue;

        if(!v[y])
        {
            t[y] = x;
            stk.emplace(x, y);
            Tarjan(y);
            low[x] = min(low[x], low[y]);

            if(low[y] >= index[x])
                ExtractCB(x, y);

        }
        else
            low[x] = min(low[x], index[y]);
    }
}

void In()
{
    cin >> n >> m;
    int u, v;

    t = low = index = VI(n + 1);
    G = VVI(n + 1);

    for(int i = 1; i <= m; ++i)
    {
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
}