Cod sursa(job #3339103)

Utilizator RaduCalisovCalisovRadu RaduCalisov Data 6 februarie 2026 12:37:27
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

struct types{
    int x;int y;int id;
};

int n,m;
int global = 1;
stack <types> st;
vector<set<int>> comp;
vector<vector<pair<int,int>>> v;
vector<int> t;
vector<bool> checked;
vector<int> low;


void addcomp(int nod,int newnod,int id){
    set<int> temp;
    while(st.size()){
        int x = st.top().x;
        int y = st.top().y;
        int newid = st.top().id;

        temp.insert(x);
        temp.insert(y);

        st.pop();

        if(newid == id)
            break;
    }
    if(temp.size())
        comp.push_back(temp);
}

void dfs(int nod,int mid){
    checked[nod] = 1;
    t[nod] = global;
    low[nod] = t[nod];
    global++;

    for(int i = 0 ;i < v[nod].size();i++){
        int newnod = v[nod][i].first;
        int id = v[nod][i].second;

        if(checked[newnod] == 0){
            st.push({nod,newnod,id});
            dfs(newnod,id);

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

            if(low[newnod] >= t[nod])
                addcomp(nod,newnod,id);

        }else if(id != mid and t[nod] > t[newnod]){
            st.push({nod,newnod,id});
            low[nod] = min(low[nod],t[newnod]);
        }
    }
}

int main(){
    fin>>n>>m;
    v.resize(n+1);
    t.resize(n+1);
    low.resize(n+1);
    checked.resize(n+1,0);

    for(int i=1;i<=m;i++){
        int x,y;
        fin>>x>>y;
        v[x].push_back({y,i});
        v[y].push_back({x,i});
    }

    for(int i=1;i<=n;i++){
        if(!checked[i])
            dfs(i,0);
    }

    fout<<comp.size()<<"\n";

    for(int i = 0;i<comp.size();i++){
        for(auto j:comp[i]){
            fout<<j<<" ";
        }
        fout<<"\n";
    }
}