Cod sursa(job #2802293)

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

vector <int> v [N] ;
vector <pii> cc [N];
stack <pii> st;
int h [N] , c1 , viz [N] , cn [N] , p;
char s [L];
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 nextInt (){
    int r (0);
    while (! isdigit (s [p])){
        ++ p;
        if (p == L){
            fread (s , 1 , L , stdin);
            p = 0;
        }
    }
    while (isdigit (s [p])){
        r = r * 10 + (s [p] - '0');
        ++ p;
        if (p == L){
            fread (s , 1 , L , stdin);
            p = 0;
        }
    }
    return r;
}
int n , m;
int main (){
    freopen ("biconex.in" , "r" , stdin);
    fread (s , 1 , L , stdin);
    n = nextInt () , m = nextInt ();
    for(int i = 1 ; i <= m ; ++ i){
        int a , b;
        a = nextInt () , b = nextInt ();
        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;
}