Cod sursa(job #3281498)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 1 martie 2025 20:30:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e5;

int n,m;
vector<int> G[nmax + 5];

bool sel[nmax + 5];
int lvl[nmax + 5], l[nmax + 5];

stack<pair<int,int>> st;

int nr;
vector<int> rez[nmax + 5];

void dfs(int nod, int dad = 0)
{
    sel[nod] = true;
    l[nod] = lvl[nod];
    for(auto it : G[nod])
    {
        if(!sel[it])
        {
            lvl[it] = 1 + lvl[nod];
            st.push({nod, it});
            dfs(it);
            l[nod] = min(l[nod], l[it]);
            if(l[it] >= lvl[nod])
            {
                ++nr;
                while(st.top().first != nod || st.top().second != it)
                {
                    rez[nr].push_back(st.top().first);
                    rez[nr].push_back(st.top().second);
                    st.pop();
                }
                rez[nr].push_back(nod);
                rez[nr].push_back(it);
                st.pop();
            }
        }
        else if(it != dad)
        {
            l[nod] = min(l[nod], lvl[it]);
        }
    }
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x, y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!sel[i])
        {
            dfs(i);
        }
    }
    cout<<nr<<'\n';
    for(int i=1;i<=nr;i++)
    {
        sort(rez[i].begin(), rez[i].end());
        auto er = unique(rez[i].begin(), rez[i].end());
        rez[i].resize(distance(rez[i].begin(), er));
        for(auto it : rez[i])
        {
            cout<<it<<' ';
        }
        cout<<'\n';
    }
    return 0;
}