Cod sursa(job #2802272)

Utilizator DordeDorde Matei Dorde Data 17 noiembrie 2021 21:01:41
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int const N = 2e5 + 3;
ifstream f ("biconex.in");
ofstream g ("biconex.out");

vector <int> v [N] ;
vector <pii> cc [N];
stack <pii> st;
unordered_map <int , bool> M;
int h [N] , c1 , viz [N];
int dfs (int node){
    int ans (h [node] + 1);
    for(auto y : v [node]){
        if (h [y] <= h [node])
            st.push (mp (node , y));
        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 () != mp (node , y)){
                cc [c1].push_back (st.top ());
                st.pop ();
            }
            cc [c1].push_back (mp (node , y));
            st.pop ();
        }
    }
    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 [x , y] : cc [i]){
            if (! M [x])
                g << x << ' ';
            if (! M [y])
                g << y << ' ';
            M [x] = M [y] = 1;
        }
        M.clear ();
        g << '\n';
    }
    return 0;
}