Cod sursa(job #2802282)

Utilizator DordeDorde Matei Dorde Data 17 noiembrie 2021 21:09:32
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 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] , cn [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){
        cn [0] = 0;
        for(auto [x , y] : cc [i]){
            cn [++ cn [0]] = x;
            cn [++ cn [0]] = y;
        }
        sort (cn + 1 , cn + cn [0] + 1);
        int l = unique (cn + 1 , cn + cn [0] + 1) - cn;
        for(int i = 1 ; i < l ; ++ i)
            g << cn [i] << ' ';
        g << '\n';
    }
    return 0;
}