Cod sursa(job #3374691)

Utilizator maria_5Diaconescu Maria maria_5 Data 9 noiembrie 2026 09:23:46
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.56 kb
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstdio>

using namespace std;

struct Muchie {
    int u, v;
};

const int NMAX = 100005;

int n, m;
vector<int> graf[NMAX];

int tin[NMAX];
int low[NMAX];
int timer = 0;

stack<Muchie> stiva;

vector<vector<int>> componente;

bool in_componenta[NMAX];

void dfs(int nod, int parinte) {
    tin[nod] = low[nod] = ++timer;

    for (int i = 0; i < (int)graf[nod].size(); i++) {
        int vecin = graf[nod][i];

        if (vecin == parinte) {
            continue;
        }

        if (tin[vecin] != 0) {
            low[nod] = min(low[nod], tin[vecin]);

            if (tin[vecin] < tin[nod]) {
                stiva.push({nod, vecin});
            }
        } else {
            stiva.push({nod, vecin});

            dfs(vecin, nod);

            low[nod] = min(low[nod], low[vecin]);

            if (low[vecin] >= tin[nod]) {
                vector<int> comp_curenta;

                while (true) {
                    Muchie m_top = stiva.top();
                    stiva.pop();

                    if (!in_componenta[m_top.u]) {
                        in_componenta[m_top.u] = true;
                        comp_curenta.push_back(m_top.u);
                    }
                    if (!in_componenta[m_top.v]) {
                        in_componenta[m_top.v] = true;
                        comp_curenta.push_back(m_top.v);
                    }

                    if (m_top.u == nod && m_top.v == vecin) {
                        break;
                    }
                }

                for (int j = 0; j < (int)comp_curenta.size(); j++) {
                    in_componenta[comp_curenta[j]] = false;
                }

                componente.push_back(comp_curenta);
            }
        }
    }
}

int main() {
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    

    if (!(cin >> n >> m)) {
        return 0;
    }

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        if (tin[i] == 0) {
            dfs(i, 0);
        }
    }

    cout << componente.size() << "\n";

    for (int i = 0; i < (int)componente.size(); i++) {
        for (int j = 0; j < (int)componente[i].size(); j++) {
            cout << componente[i][j] << (j + 1 == (int)componente[i].size() ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}