Cod sursa(job #2814770)

Utilizator Albert_GAlbert G Albert_G Data 8 decembrie 2021 16:24:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include <fstream>
#include <vector>
#include <stack>

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

const int N = 1e5+1;
int n, m, t[N], t_min[N], curr_time, curr_cbc;
std::vector<int> g[N], cbc[N];
std::stack<int> st;

/*const int N = 1e5+1;
int n, m, t[N], t_min[N], curr_time;
std::vector<int> g[N], p_art;

// puncte de articulatie
void dfs(int curr_node, int tata){
    t_min[curr_node] = t[curr_node] = ++curr_time;
    int nr_fii = 0;
    for(auto fiu : g[curr_node]){
        if(t[fiu] == 0){ //fiu nevizitat
            ++nr_fii;
            dfs(fiu, curr_node);
            t_min[curr_node] = std::min(t_min[curr_node], t_min[fiu]);
            if(t_min[fiu] >= t[curr_node] && tata != 0){
                p_art.push_back(curr_node); //curr_node -> este punct de articulatie
            }
        }
        else if(fiu != tata){
            t_min[curr_node] = std::min(t_min[curr_node], t[fiu]);
        }
    }
    if(tata == 0 && nr_fii > 1){
        p_art.push_back(curr_node);
    }
}
*/

void add_cbc(int x, int y){
    ++curr_cbc;
    while(st.top() != y){
        cbc[curr_cbc].push_back(st.top());
        st.pop();
    }
    cbc[curr_cbc].push_back(y);
    st.pop();
    cbc[curr_cbc].push_back(x);
}

void dfs(int curr_node, int tata){
    t_min[curr_node] = t[curr_node] = ++curr_time;
    st.push(curr_node);
    for(auto fiu : g[curr_node]){
        if(t[fiu] == 0){ //fiu nevizitat
            dfs(fiu, curr_node);
            t_min[curr_node] = std::min(t_min[curr_node], t_min[fiu]);
            if(t_min[fiu] >= t[curr_node]){
                add_cbc(curr_node, fiu);
            }
        }
        else if(fiu != tata){
            t_min[curr_node] = std::min(t_min[curr_node], t[fiu]);
        }
    }
}

int main(){
    in>>n>>m;
    for(int i=0;i<m;++i){
        int a,b;
        in>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 1; i <= n; ++i){
        if(t[i] != 0) continue;
        dfs(i, 0);
    }
    out<< curr_cbc << '\n';
    for(int i = 1; i <= curr_cbc; ++i){
        for(auto x : cbc[i])
            out << x << ' ';
        out << '\n';
    }
    in.close();
    out.close();
    return 0;
}