Cod sursa(job #3186934)

Utilizator antonio_sefu_tauLaslau Antonio antonio_sefu_tau Data 26 decembrie 2023 16:48:13
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>
using namespace std;
const int dim=1e5+5;
int n,m,dfn[dim],low[dim],timer,fii,art[dim],nr;
vector<int> G[dim];
vector<pair<int,int>> sol[dim];
stack<pair<int,int>> st;
void comp_biconexa(int u, int v){
    nr++;
    pair<int,int> muc;
    do{
        muc=st.top();
        st.pop();
        sol[nr].push_back(muc);
    }while(!(muc.first==u and muc.second==v));
}
void biconex(int nod, int tata){
    dfn[nod]=low[nod]=++timer;
    for(auto x:G[nod]){
        if(x!=tata and dfn[x]<dfn[nod]){
            st.push({x,nod});
        }
        if(dfn[x]==-1){
            if(nod==1){
                fii++;
            }
            biconex(x,nod);
            low[nod]=min(low[nod],low[x]);
            if(low[x]>=dfn[nod]){
                if(nod!=1){
                    art[nod]=1;
                }
                comp_biconexa(x,nod);
            }
        }
        else{
            if(x!=tata){
                low[nod]=min(low[nod],dfn[x]);
            }
        }
    }
}
int main(){
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    f>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        dfn[i]=low[i]=-1;
    }
    st.push({1,-1});
    biconex(1,-1);
    if(fii>=2){
        art[1]=1;
    }
//    for(int i=1;i<=n;i++){
//        if(art[i]){
//            cout<<i<<' ';
//        }
//    }
    g<<nr<<'\n';
    for(int i=1;i<=nr;i++){
        map<int,bool> fr;
        for(auto x:sol[i]){
            fr[x.first]=1;
            fr[x.second]=1;
        }
        for(auto x:fr){
            g<<x.first<<' ';
        }
        g<<'\n';
    }
    return 0;
}