Cod sursa(job #2802253)

Utilizator DordeDorde Matei Dorde Data 17 noiembrie 2021 20:48:17
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;
int const N = 2e5 + 3;
ifstream f ("biconex.in");
ofstream g ("biconex.out");

vector <int> v [N] , cc [N];
stack <int> st;
int h [N] , c1;
int dfs (int node){
    int ans (h [node] + 1);
    st.push (node);
    for(auto y : v [node]){
        if (h [y]){
            ans = min (ans , h [y]);
            continue;
        }
        h [y] = 1 + h [node];
        int x = dfs (y);
        ans = min (ans , x);
        if (x >= h [node]){
            ++ c1;
            while (st.size () && st.top () != node){
                cc [c1].push_back (st.top ());
                st.pop ();
            }
            cc [c1].push_back (node);
        }
    }
    return ans;
}
int n , m;
int main (){
    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);
    }
    for(int i = 1 ; i <= n ; ++ i)
        if (! h [i]){
            h [i] = 1;
            dfs (i);
        }
    g << c1 << '\n';
    for(int i = 1 ; i <= c1 ; ++ i){
        for(auto j : cc [i])
            g << j << ' ';
        g << '\n';
    }
    return 0;
}