Cod sursa(job #3320359)

Utilizator RaduCalisovCalisovRadu RaduCalisov Data 5 noiembrie 2025 12:38:38
Problema Componente biconexe Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int>> v;
vector<vector<int>> bicomp;
vector<bool> checked;
vector<int> depth;
vector<int> low;

stack <int> q;

void dfs(int nod,int p,int root){
    q.push(nod);
    
    checked[nod] = 1;
    low[nod] = depth[nod];

    bool verified = false;

    for(int i=0;i<v[nod].size();i++){
        int newnod = v[nod][i];
        if(p == newnod)
            continue;
        if(checked[newnod] == 1)
            low[nod] = min(low[nod],depth[newnod]);
        else{
            depth[newnod] = depth[nod] + 1;
            dfs(newnod,nod,root);

            low[nod] = min(low[nod],low[newnod]);

            if(low[newnod] >= depth[nod] and verified == false){
                verified = true;

                vector<int> comp;

                while(q.size()){
                    int top = q.top();
                    comp.push_back(top);

                    if(top == nod)
                        break;
                    q.pop();
                }

                bicomp.push_back(comp);
            }
        }
    }
    if(root==nod and q.size()){
        vector<int> comp;

        while(q.size()){
            int top = q.top();
            q.pop();
            comp.push_back(top);

            if(top == nod)
                break;
        }

        bicomp.push_back(comp);
    }
}

int main(){
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    
    cin>>n>>m;    
    v.resize(n+1);
    checked.resize(n+1,0);
    depth.resize(n+1,0);
    low.resize(n+1);
    
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;

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

    dfs(1,1,1);  

    cout<<bicomp.size()<<"\n";
    for(int i = 0 ; i<bicomp.size(); i++){
        for(int j = 0 ; j < bicomp[i].size(); j++)
            cout<<bicomp[i][j]<<" ";
        cout<<"\n";
    }
}