Cod sursa(job #2801633)

Utilizator DordeDorde Matei Dorde Data 16 noiembrie 2021 17:54:50
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
int const N = 1e5 + 3;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
vector <int> v [N];
vector <int> ans [2 * N];
stack <int> st;
int cb , h [N] , niv [N];
bool viz [N];
int dfs (int node){
    viz [node] = true;
    st.push (node);
    for(auto y : v [node]){
        if (viz [y]){
            niv [node] = min (niv [node] , h [y]);
            continue;
        }
        else{
            h [y] = 1 + h [node];
            int ant = dfs (y);
            if (ant >= h [node]){
                ++ cb;
                while (st.size () && st.top () != node){
                    ans [cb].push_back (st.top ());
                    auto O = st.top();
                    st.pop ();
                }
                ans [cb].push_back (st.top ());
            }
            niv [node] = min (niv [node] , ant);
        }
    }
    return niv [node];
}
int main()
{
    int n , m ;
    f >> n >> m;
    for(int i = 1 ; i <= m ; ++ i){
        int a , b;
        f >> a >> b;
        v [a].push_back (b);
        v [b].push_back (a);
    }
    fill (niv , niv + 1 + n , (1 << 30));
    dfs (1);
    g << cb << '\n';
    for(int i = 1 ; i <= cb ; ++ i){
        for(auto j : ans [i]){
            g << j << ' ';
        }
        g << '\n';
    }
    return 0;
}