Cod sursa(job #2677543)

Utilizator Iustin01Isciuc Iustin - Constantin Iustin01 Data 26 noiembrie 2020 19:44:31
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
#define MAX 100005
using namespace std;

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

vector < int > g[MAX], sol[MAX];
bitset < MAX > c;
stack < int > st;
int n, m, x, y, nivel[MAX], nma[MAX], nrcbx;


void dfs(int k, int tata){
    c[k] = true;
    st.push(k);
    for(int i = 0; i < g[k].size(); i++){
        int vec = g[k][i];
        if(!c[vec]){
            nivel[vec] = nivel[k] + 1;
            nma[vec] = nivel[vec];
            dfs(vec, k);
            nma[k] = min(nma[k], nma[vec]);

            if(nivel[k] <= nma[vec]){
            nrcbx++;
            sol[nrcbx].push_back(k);
            while(st.top() != vec){
                sol[nrcbx].push_back(st.top());
                st.pop();
            }
                sol[nrcbx].push_back(st.top());
                st.pop();
        }
        }
        else
            if(tata != vec)
                nma[k] = min(nma[k], nivel[vec]);

    }
}

int main(){
    in>>n>>m;
    for(int i = 1; i <= m; i++){
        in>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, 0);
    out<<nrcbx<<"\n";
    for(int i = 1; i <= nrcbx; i++, out<<"\n")
        for(int j = 0; j < sol[i].size(); j++)
            out<<sol[i][j]<<" ";


}