Cod sursa(job #2815817)

Utilizator AndreeaGherghescuAndreea Gherghescu AndreeaGherghescu Data 10 decembrie 2021 14:19:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int N = 100001;
const int M = 200001;

int n,m, urm[M*2], lst[N], vf[2*M],nr,nivel[N],niv_min[N],stk[N],k,nbc;
vector <int> cmp_b [N];

void adauga (int x, int y) {
    vf[++nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
}
void dfs (int x, int parent) {
    niv_min[x] = nivel[x];
    stk[++k] = x;
    for (int p = lst[x]; p != 0; p = urm[p]) {
        int y = vf[p];
        if (y == parent) continue;
        if (!nivel[y] ) {
            nivel[y] = nivel[x] + 1;
            dfs(y,x);
            if (niv_min[y] >= nivel[x]) {
                nbc++;
                while (k && stk[k] != y) {
                    cmp_b[nbc].push_back(stk[k--]);
                }
                cmp_b[nbc].push_back(stk[k--]);
                cmp_b[nbc].push_back(x);
            }
            niv_min[x] = min(niv_min[x], niv_min[y]);
        }
        else {
            niv_min[x] = min(niv_min[x], nivel[y]);
        }
    }
}
int main() {
    in>>n>>m;
    int x,y;
    for (int i=0;i<m;i++) {
        in>>x>>y;
        adauga(x,y);
        adauga(y,x);
    }

    for (int i=1;i<=n;i++) {
        if (!nivel[i])
            dfs(i,0);
    }
    out<<nbc<<'\n';
    for (int i = 1; i <= nbc; i++) {
        for (int j = 0; j < cmp_b[i].size(); j++) {
            out<<cmp_b[i][j]<<' ';
        }
        out<<'\n';
    }
    return 0;
}