Cod sursa(job #3374908)

Utilizator teogrecigrecioiu teo teogreci Data 9 noiembrie 2026 18:40:04
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int nmax = 100005;
int n, m;
vector<int> g[nmax];
int nivel[nmax];
int low[nmax];
int timp;
int stiva[nmax], vf;
vector<int> componente[nmax];
int nrComponente;

void dfs(int x, int parinte) {
    nivel[x] = low[x] = ++timp;
    stiva[++vf] = x;

    for (int k = 0; k < (int)g[x].size(); k++) {
        int y = g[x][k];
        if (y == parinte)
            continue;
        if (nivel[y] != 0) {
            if (nivel[y] < low[x])
                low[x] = nivel[y];
        } else {
            dfs(y, x);
            if (low[y] < low[x])
                low[x] = low[y];
            if (low[y] >= nivel[x]) {
                nrComponente++;
                while (stiva[vf] != y) {
                    componente[nrComponente].push_back(stiva[vf]);
                    vf--;
                }
                componente[nrComponente].push_back(y);
                vf--;
                componente[nrComponente].push_back(x);
            }
        }
    }
}
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 (nivel[i] == 0)
            dfs(i, 0);

    fout << nrComponente << "\n";
    for (int i = 1; i <= nrComponente; i++) {
        for (int j = 0; j < (int)componente[i].size(); j++)
            fout << componente[i][j] << " ";
        fout << "\n";
    }
    return 0;
}