Cod sursa(job #3374577)

Utilizator gabiaAygan Gabriela Aylin gabia Data 9 noiembrie 2026 02:40:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <vector>
using namespace std;

// Componente biconexe cu un DFS:
//   niv[x] = momentul la care am intrat in x
//   low[x] = cel mai mic niv la care putem ajunge din subarborele lui x
//            folosind cel mult o muchie de intoarcere
// Tinem o stiva cu nodurile vizitate. Cand pentru un fiu y al lui x avem
// low[y] >= niv[x], inseamna ca x separa subarborele lui y de restul grafului
// (x e punct de articulatie sau radacina), deci nodurile scoase din stiva
// pana la y, impreuna cu x, formeaza o componenta biconexa.

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

const int NMAX = 100005;

int n, m;
vector<int> G[NMAX];
int niv[NMAX], low[NMAX];
int stiva[NMAX], varf;
int timp;
int nrComp;
vector<int> comp[NMAX];

void dfs(int x) {
    timp++;
    niv[x] = low[x] = timp;
    varf++;
    stiva[varf] = x;

    for (size_t k = 0; k < G[x].size(); k++) {
        int y = G[x][k];
        if (niv[y] == 0) {
            dfs(y);
            if (low[y] < low[x])
                low[x] = low[y];
            if (low[y] >= niv[x]) {
                nrComp++;
                int z;
                do {
                    z = stiva[varf];
                    varf--;
                    comp[nrComp].push_back(z);
                } while (z != y);
                comp[nrComp].push_back(x);
            }
        } else {
            if (niv[y] < low[x])
                low[x] = niv[y];
        }
    }
}

int main() {
    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);
    }

    for (int i = 1; i <= n; i++)
        if (niv[i] == 0)
            dfs(i);

    fout << nrComp << "\n";
    for (int i = 1; i <= nrComp; i++) {
        for (size_t k = 0; k < comp[i].size(); k++)
            fout << comp[i][k] << " ";
        fout << "\n";
    }

    return 0;
}