Cod sursa(job #3293535)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 11 aprilie 2025 21:29:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3")
using namespace __gnu_pbds;
using oset=tree<int,null_type,std::less<int>,rb_tree_tag,tree_order_statistics_node_update>;
#define all(x) x.begin(),x.end()
using i64 =long long;
const int N_MAX=1e5;
const int inf=1e9;
int n,m;
int tin[N_MAX],low[N_MAX];
std::vector<int>adj[N_MAX];
std::stack<std::pair<int,int>>sk;
std::vector<std::vector<int>>comps;
void pop_till(int x,int y)
{
    std::vector<int>aux;
    while(sk.top().first!=x || sk.top().second!=y)
    {
        aux.push_back(sk.top().first);
        aux.push_back(sk.top().second);
        sk.pop();
    }
    aux.push_back(x);
    aux.push_back(y);
    sk.pop();

    std::sort(all(aux));
    aux.erase(std::unique(all(aux)),aux.end());
    comps.push_back(aux);
}
void dfs(int nod,int tt)
{
    static int time=0;
    tin[nod]=low[nod]=++time;
    for(auto &c:adj[nod])
    {
        if(c==tt)
        {
            continue;
        }
        if(low[c]==0)
        {
            sk.push({nod,c});
            dfs(c,nod);
            low[nod]=std::min(low[nod] , low[c]);
            if(low[c]>=tin[nod])
            {
                pop_till(nod,c);
            }
        }
        else
        {
            low[nod]=std::min(low[nod] , tin[c]);
        }
    }
}
[[gnu::optimize("O3")]]signed main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y;
        std::cin>>x>>y;
        x--;
        y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(0,0);
    std::cout<<comps.size()<<'\n';
    for(auto &v:comps)
    {
        for(auto &c:v)
        {
            std::cout<<c+1<<' ';
        }
        std::cout<<'\n';
    }
    return 0;
}