Cactus without Bridges 详细题解

一、题意梳理

1. 基础定义

1. 桥：删去后连通块数量增加的边，本题给定图无桥。
2. 仙人掌图：连通无向图，每条边至多属于一个简单环，无重边、无自环。
3. 附加限制：图中每个奇简单环长度 $\ge$ 整张图内奇简单环总个数。

2. 边标号要求

设最大标号为 $t$，需满足：

1. 标号恰好使用 $1,2,\dots,t$ 所有正整数；
2. 对任意顶点 $v$，所有邻边标号互不相同，且构成一段连续整数区间；
3. 标号均为正整数。

3. 数据范围

$3\le n\le 10^5,\ n\le m\le \left\lfloor\dfrac{3(n-1)}{2}\right\rfloor$

二、核心解题结论

1. 无解充要条件：图中存在长度为奇数的简单环，直接输出 $\texttt{NO}$；
2. 有解充分条件：整张图所有环均为偶环，一定可以构造出合法边标号；
3. 题目给出「奇环长度 $\ge$ 奇环总数」仅为出题前置约束，不影响解题判定与构造。

样例1为$5$阶奇环，直接判定无解，输出$\texttt{NO}$。

三、证明简略

1. 若存在奇环：无法让环上每个点邻边标号形成连续区间，必然矛盾；
2. 偶环可采用**$1,2$交替染色**，环上每个点度数为$2$，两个标号天然构成连续区间$[1,2]$；
3. 度数大于$2$的汇聚点，顺着已有最大标号向后顺延赋值，保证邻边标号整体连续。

四、算法整体思路

1. DFS遍历仙人掌，借助深度数组找所有简单环；
2. 计算环长，一旦发现奇环直接终止程序输出无解；
3. 对所有偶环执行1、2交替边标号；
4. 二次DFS处理分支多余边，从当前最大标号向后顺推赋值；
5. 最终输出最大标号$t$与所有边标号。

五、标程变量释义

const int MAXN = 1e5 + 5;
const int MAXM = 3e5 + 5;
vector<pair<int,int>> adj[MAXN]; // 邻接表：(邻点,边编号)
pair<int,int> edges[MAXM];      // 存储原始输入边
int ans[MAXM];                   // ans[i] 表示第i条边的标号
bool vis[MAXN];                  // 访问标记
int fa[MAXN];                    // 父节点
int fe[MAXN];                    // 指向父节点的边编号
int dep[MAXN];                   // 节点深度
int t;                           // 全局最大标号

六、核心函数详解

1. 第一轮DFS：找环 + 判奇偶 + 偶环基础染色

void dfs(int u, int father)
{
    vis[u] = true;
    fa[u] = father;
    for(auto [v,eid]:adj[u])
    {
        if(v == father) continue;
        if(!vis[v])
        {
            dep[v] = dep[u] + 1;
            fe[v] = eid;
            dfs(v,u);
        }
        // 遇到回边，找到一个简单环
        else if(dep[v] < dep[u])
        {
            int len = dep[u] - dep[v] + 1;
            // 发现奇环，直接无解
            if(len % 2 == 1)
            {
                cout<<"NO\n";
                exit(0);
            }
            // 偶环 1、2交替赋值
            int cur = u;
            int col = 1;
            while(cur != v)
            {
                ans[fe[cur]] = col;
                t = max(t,col);
                col = 3 - col; // 1<->2 互换
                cur = fa[cur];
            }
            ans[eid] = col;
            t = max(t,col);
        }
    }
}

• 利用深度差计算环长 $\mathit{len}=dep[u]-dep[v]+1$；
• $3-col$ 快速实现 $1$ 与 $2$ 交替；
• 遍历环上所有树边完成染色，最后给回边赋值收尾。

2. 第二轮DFS：处理分叉边，保证区间连续

void dfs2(int u, int father)
{
    vector<int> es;
    // 收集当前点未赋值的多余分支边
    for(auto [v,eid]:adj[u])
    {
        if(eid != fe[u] && ans[eid]==0)
            es.push_back(eid);
    }
    // 从当前最大标号往后顺延赋值
    int now = t + 1;
    for(int e:es)
    {
        ans[e] = now++;
    }
    t = max(t, now-1);
    // 继续向下遍历
    for(auto [v,eid]:adj[u])
    {
        if(v != father && !vis[v])
        {
            vis[v] = true;
            dfs2(v,u);
        }
    }
}

• 度数大于$2$的节点会存在未染色分支边；
• 从$t+1$依次递增赋值，天然保证该点所有邻边标号连成连续整数；
• 同时保证全局标号填满$1\sim t$。

七、主函数流程

1. 读入点数$n$、边数$m$，建图存边；
2. 初始化深度数组，从$1$号点开始第一轮$\text{DFS}$判环染色；
3. 清空访问标记，执行第二轮$\text{DFS}$补全剩余边标号；
4. 按格式输出：$\texttt{YES}$、最大标号$t$、所有边标号。

八、合法性验证

1. 同点边标号互不相同：环内交替1/2，分支顺推递增，无重复；
2. 构成连续区间：汇聚点所有邻边标号是一段紧挨着的整数；
3. 铺满$1\sim t$：从小到大依次使用所有整数，无空缺；
4. 复杂度：两轮线性$\text{DFS}$，总复杂度 $O(n+m)$，可稳过 $10^5$ 级别数据。

九、易错点提醒

1. 仙人掌图找环只能用回边+深度差，不能通用无向图判环写法；
2. 必须区分树边与回边，避免重复处理同一个环；
3. 奇环一旦出现必须立刻退出程序，不能继续构造；
4. 边编号严格对应输入顺序，输出顺序不能错乱。