Cod sursa(job #3320052)

Utilizator Mirc100Mircea Octavian Mirc100 Data 4 noiembrie 2025 10:09:21
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
vector<int>niv;
vector<int>niv_min;
vector<int>G[100005];
stack<pair<int,int>>st;
int n,m;
ifstream f("biconex.in");
ofstream g("biconex.out");

vector<vector<int>> comps;

void dfs(int nod, vector<int>& viz){
    viz[nod]=1;
    niv_min[nod]=niv[nod];

    for(auto y : G[nod]){
        if(viz[y]==0){
            st.push({nod,y});
            niv[y]=niv[nod]+1;
            dfs(y, viz);
            if(niv[nod] <= niv_min[y]){
                vector<int> comp;
                pair<int,int> mc;
                do{
							mc=st.top();
							st.pop();

							comp.push_back(mc.second);
                }while(mc.first!=nod || mc.second!=y );
                comp.push_back(nod);
                comps.push_back(comp);

            }

            niv_min[nod]=min(niv_min[nod], niv_min[y]);
        }
        else{
            if(niv[y] < niv[nod]-1){
                niv_min[nod]=min(niv_min[nod], niv[y]);
            }
        }
    }

}
int main(){

    vector<int>viz;
    f>>n>>m;


    viz.assign(n+1, 0);
    niv.assign(n+1, 0);
    niv_min.assign(n+1, 0);

    for( int i=0;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++)
        if(viz[i]==0)
            dfs(i, viz);
    g<<comps.size()<<"\n";
    for(auto &comp:comps){
        for(auto x:comp)
            g<<x<<" ";
        g<<"\n";
    }
    g.close();
    f.close();



}