Cod sursa(job #3364371)

Utilizator CarenaMironov Cezar Luca Carena Data 2 septembrie 2026 12:40:22
Problema Componente biconexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

const int NMAX=1e5+5;
int n, m, depth[NMAX], dp[NMAX], art[NMAX], viz[NMAX];
vector<int> adj[NMAX];
vector<vector<int>> bcc;

void DFSdp(int u, int pu)
{
    bool lf=1;
    depth[u]=depth[pu]+1;
    for(auto v:adj[u])
    {
        if(v==pu || depth[v]>depth[u])
            continue;
        if(depth[v]==0)
        {
            lf=0;
            DFSdp(v, u);
            dp[u]+=dp[v];
        }
        else
        {
            dp[pu]++;
            dp[v]--;
        }
    }
    art[u]=(!lf && dp[u]==0);
}

void DFSbcc(int u)
{
    viz[u]=1;
    for(auto v:adj[u])
    {
        if(viz[v] || abs(depth[u]-depth[v])!=1)
            continue;
        bcc.back().push_back(v);
        if(!art[v])
            DFSbcc(v);
    }
}

int main()
{
    in>>n>>m;
    while(m--)
    {
        int a, b; in>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    DFSdp(1, 0);
    for(int i=1;i<=n;i++)
        if(art[i])
            for(auto j:adj[i])
                if(!viz[j] && abs(depth[i]-depth[j])==1)
                {
                    if(!art[j])
                    {
                        bcc.push_back({j});
                        DFSbcc(j);
                    }
                    else if(i<j)
                        bcc.push_back({i, j});
                }
    
    out<<bcc.size()<<'\n';
    for(auto b:bcc)
    {
        for(auto u:b)
            out<<u<<" ";
        out<<'\n';
    }
    return 0;
}