Cod sursa(job #3307637)

Utilizator Tudor_CCTudor Cocu Tudor_CC Data 22 august 2025 13:17:57
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> v[100555];

int d[100555];

int l[100555];

int p[100555];

vector <int> cbc[1000555];

vector <int> st;

int in;

void dfs(int u,int k)
{
    d[u]=k;
    l[u]=k;
    for(auto a:v[u])
    {
        if(a!=p[u])
        {


        if(p[a]==0)
        {
        p[a]=u;
        st.push_back(u);
        st.push_back(a);
        dfs(a,k+1);
        l[u]=min(l[u],l[a]);
        if(l[a]>=d[u])
        {
            ++in;
            bool ok=false;
            while(ok==false && st.size()>0)
            {
                cbc[in].push_back(st[st.size()-1]);
                cbc[in].push_back(st[st.size()-2]);
                if(st[st.size()-1]==a && st[st.size()-2]==u)
                {
                    ok=true;
                }
                st.pop_back();
                st.pop_back();
            }
        }
        }
        else if(d[a]<d[u])
        {
        l[u]=min(l[u],d[a]);
        st.push_back(u);
        st.push_back(a);
        }
        }
    }

}

int main()
{
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    int n,m,x,y;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
    {
        if(d[i]==0)
        {
            p[i]=-1;
            dfs(i,1);
        }
    }
    cout<<in<<"\n";
    for(int i=1;i<=in;++i)
    {
        sort(cbc[i].begin(),cbc[i].end());
        for(int h=0;h<cbc[i].size();++h)
        {
            if(h==0 || cbc[i][h]!=cbc[i][h-1])
            {
                cout<<cbc[i][h]<<" ";
            }
        }
        cout<<"\n";
    }
    return 0;
}