Cod sursa(job #3318728)

Utilizator pstgarain ploaie pstga Data 28 octombrie 2025 15:27:00
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <bits/stdc++.h>
using namespace std;

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

#define MAXN  100005
// zona de declarare
int n, m;
vector <int> adj[MAXN]; // adiacenta
int niv[MAXN+1], low[MAXN+1]; // niv low
vector <vector <int> > C; // matricea rezultat cu ciclurile
stack <pair <int, int> > stk; // stackul de noduri/muchii in componenta biconexa

void extract(const int x, const int y) // introducerea componentei in rezultat
{
    vector <int> con; int tx, ty;
    do {
        tx = stk.top().first, ty = stk.top().second; // iau cate o muchie
        stk.pop();
        con.push_back(tx), con.push_back(ty);
    }
    while (tx != x || ty != y);
    C.push_back(con); // muchie cu muchie
}

void DF(const int n, const int fn)
{
    niv[n] = low[n] = niv[fn]+1;
    for (auto it : adj[n]) {
        if (it == fn)   continue ; // se repeta e ciclu cvcv
        if (niv[it] == -1) { // nevizitat
            stk.push( make_pair(n, it) ); // imi pune muchia pe stack
            DF(it, n);
            low[n] = min(low[n], low[it]); // actualizam low ul
            if (low[it] >= niv[n])
                extract(n, it); // capatul componentei biconexe
        }
        else
            low[n] = min(low[n], niv[it]);
    }
}

int main()
{
    // citire si initializare
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for (int i = 0; i <= n; i++) {
        niv[i] = low[i] = -1;
    }

    // apelarea algoritmului
    DF(1, 0);

    // afisarea de date
    fout << C.size() << "\n";
    for (int i = 0; i < C.size(); ++ i) {
        sort(C[i].begin(), C[i].end());
        C[i].erase(unique(C[i].begin(), C[i].end()), C[i].end()); // sterge duplicatele
        for (int j = 0; j < C[i].size(); ++ j)
            fout << C[i][j] << " ";
        fout << "\n";
    }
    return 0;
}