Cod sursa(job #2886808)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 8 aprilie 2022 13:14:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;
const int NMAX = 1e5, NOTVIS = 1e9;

struct edge {
    int nd1, nd2;
};

vector<vector<int>> bi;
vector<int> adj[NMAX + 1];
edge stk[NMAX + 1];
int h[NMAX + 1], father[NMAX + 1], sp;

int findBi(int nd);
void pushBi(edge e);

int main() {

    int n, m, nd1, nd2;
    FILE *fin = fopen("biconex.in", "r");

    fscanf(fin, "%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        fscanf(fin, "%d%d", &nd1, &nd2);

        adj[nd1].push_back(nd2);
        adj[nd2].push_back(nd1);
    }
    fclose(fin);

    for (int i = 0; i <= n; i++)
        h[i] = NOTVIS;

    h[1] = 0, father[1] = 0;
    findBi(1);

    FILE *fout = fopen("biconex.out", "w");
    fprintf(fout, "%d\n", bi.size());
    for (vector<int> curr: bi) {
        for (int nd: curr)
            fprintf(fout, "%d ", nd);
        fprintf(fout, "\n");
    }
    fclose(fout);

    return 0;
}

int findBi(int nd) {
    int reach = h[nd];

    for (int nxt: adj[nd])
        if (h[nxt] == NOTVIS) {
            h[nxt] = h[nd] + 1;
            stk[++sp] = {nd, nxt};
            father[nxt] = nd;
            reach = min(reach, findBi(nxt));
        }
        else if (nxt != father[nd])reach = min(reach, h[nxt]);

    if (reach >= h[father[nd]])
        pushBi({father[nd], nd});
    return reach;
}
void pushBi(edge e) {
    vector<int> currBi;
    while (sp > 0 && (stk[sp].nd1 != e.nd1 || stk[sp].nd2 != e.nd2))
        currBi.push_back(stk[sp--].nd2);
    currBi.push_back(stk[sp].nd2);
    currBi.push_back(stk[sp--].nd1);
    bi.push_back(currBi);
}