Cod sursa(job #2982072)

Utilizator gabriel10tm@gmail.comGabriel Marian [email protected] Data 19 februarie 2023 15:08:56
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
const int nmx = 1e5 + 4;
vector<int> ad[nmx];
int low[nmx],h[nmx],vis[nmx];
int nc[nmx];
vector<vector<int>> cxx={{}};
#if 1
#define cin fin
#define cout fout
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#endif // 1
void dfs(int k,int t){
    int nrfi = 0;
    vis[k] = 1;
    h[k] = h[t] + 1;
    low[k] = h[k];
    for(int to : ad[k]){
        if(vis[to] == 0){
            nrfi++;
            dfs(to,k);
            low[k] = min(low[k],low[to]);
            if(low[to]>=h[k]){
                nc[k] = 1;
                cxx.back().push_back(k);
                cxx.push_back({});
            }
        }
        else // just using 1 back edge
            low[k] = min(low[k],h[to]);
    }
    if(t == 0){
        if(nrfi==1)
            nc[k] = 0;
    }
    else
        cxx.back().push_back(k);
}
int main(){
    int n,m;
    cin >> n >> m;
    while(m--){
        int u,v;
        cin >> u >> v;
        ad[u].push_back(v);
        ad[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        if(vis[i]==0)
            dfs(i,0);
    for(auto& cx : cxx){
        for(int el : cx)
            cout << el << " ";
        cout << "\n";
    }
}