Cod sursa(job #3376002)

Utilizator horia.boeriuBoeriu Horia Andrei horia.boeriu Data 15 noiembrie 2026 00:19:45
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 100000;
const int MAXM = 200000;
int d[MAXN + 1], low[MAXN + 1], stx[MAXM], sty[MAXM], fr[MAXN + 1];
vector<int> adj[MAXN + 1];
vector<int> vcomp[MAXM + 1];
int nro, vf, nrc;
int minim(int a, int b) {
    return a < b ? a : b;
}
void findComp(int x, int y) {//gasesc componenta biconexa si scot muchiile ei din stiva
    nrc++;
    do {
        vf--;
        if (fr[stx[vf]] < nrc) {
            vcomp[nrc].push_back(stx[vf]);
        }
        if (fr[sty[vf]] < nrc) {
            vcomp[nrc].push_back(sty[vf]);
        }
        fr[stx[vf]] = fr[sty[vf]] = nrc;
    } while (stx[vf] != x || sty[vf] != y);
}
void dfs(int nod, int par) {
    int nr, i, x;
    nro++;
    d[nod] = low[nod] = nro;
    nr = adj[nod].size();
    for (i = 0; i < nr; i++) {
        x = adj[nod][i];
        if (d[x] == 0) {
            stx[vf] = x;
            sty[vf] = nod;
            vf++;
            dfs(x, nod);
            low[nod] = minim(low[nod], low[x]);
            if (low[x] >= d[nod]) {//este o componenta biconexa
                findComp(x, nod);
            }
        } else if (x != par) {
            if (d[x] < d[nod]) {//back edge
                low[nod] = minim(low[nod], low[x]);

                stx[vf] = x;
                sty[vf] = nod;
                vf++;
            }
        }
    }
}
int main()
{
    FILE *fin, *fout;
    int n, i, m, x, y, nr, j;
    fin = fopen("biconex.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for (i = 0; i < m; i++) {
        fscanf(fin, "%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    fclose(fin);
    dfs(1, 0);
    fout = fopen("biconex.out", "w");
    fprintf(fout, "%d\n", nrc);
    for (i = 1; i <= nrc; i++) {
        nr = vcomp[i].size();
        for (j = 0; j < nr; j++) {
            fprintf(fout, "%d ", vcomp[i][j]);
        }
        fprintf(fout, "\n");
    }
    fclose(fout);
    return 0;
}