Cod sursa(job #2697128)

Utilizator QubeeStefan Ste Qubee Data 17 ianuarie 2021 18:34:07
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
using namespace std;

ifstream r("biconex.in");
ofstream w("biconex.out");

int n, m, v[100002], h[100002], cnt;
vector <int> g[100002], ans[100002];
stack <int> st;

void dfs(int a, int b){

    v[a] = h[a] = v[b] + 1;
    st.push(a);

    for(auto it : g[a])
        if(it == b){
            continue;
        }
        else{
            if(v[it]){
                h[a] = min(h[a], v[it]);
                continue;
            }
            dfs(it, a);

            h[a] = min(h[a], h[it]);

            if(v[a] <= h[it]){

                cnt++;
                int k;
                do{
                    k = st.top();
                    st.pop();
                    ans[cnt].push_back(k);
                }while(k != it);

                ans[cnt].push_back(a);
            }
        }
}

int main(){

    r>>n>>m;

    for(int i = 1; i <= m; i++){

        int x, y;
        r >> x >> y;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i = 1; i <= n; i++){
        if(!v[i]){
            dfs(i, 0);
        }
    }

    w << cnt<<"\n";

    for(int i = 1; i <= cnt; i++){
        for(auto it : ans[i]){
            w << it <<" ";

        }
        w <<"\n";
    }
    return 0;
}