Cod sursa(job #3320362)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 5 noiembrie 2025 13:06:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 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 <pair<int,int>> q;

void dfs(int nod,int p,int root){
    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;
            q.push({nod,newnod});
            dfs(newnod,nod,root);

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

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

                vector<int> comp;
                comp.push_back(nod);

                while(q.size()){
                    int x = q.top().first;
                    int y = q.top().second;
                    q.pop();
                    
                    comp.push_back(y);

                    if(x == nod and y==newnod)
                        break;
                }

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

    //     comp.push_back(nod);
        
    //     while(q.size()){
    //        int x = q.top().first;
    //        int y = q.top().second;
    //        q.pop();
             
    //        comp.push_back(y);
    //      }

    //      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";
    }
}