分离的路径

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1975 字
给定F个草场、R条双向道路的连通无向图，求最
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1520
// 题意：给定 F 个草场、R 条双向道路的连通无向图，求最少新建几条路，使任意两点间都有两条边不相交的路径。
// 思路：Tarjan 求出所有桥，删掉桥后把剩下的边双连通分量缩成点得到一棵桥树，设桥树叶结点数为 leaf，答案就是 (leaf + 1) / 2。
// 1. 缩点后桥树上每片叶子都只靠一条桥连着，把两片叶子连起来就能同时消掉它们到根路径上的桥。
// 2. 两两配对后最多剩一片叶子，再连一条即可，所以是叶子数加一后除以二。
// 复杂度：O(F + R) 时间 / O(F + R) 空间
// 易错点：两点之间允许有重边，判桥时必须按边的下标（互为反向的两条边下标异或 1）跳过，不能用「v == 父亲」跳过，否则重边会被误判成桥。
// 易错点：染色缩点时既要跳过桥边也要跳过已染色点，且无桥时整图只有一个分量，此时 leaf = 0，答案算出来正好是 0。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
const int MAXM = 20005;
int head[MAXN], to[MAXM], nxt[MAXM], eid[MAXM], ecnt = 1;
int dfn[MAXN], low[MAXN], idx;
int comp[MAXN], deg[MAXN], ccnt;
bool isbridge[MAXM];
void add(int u, int v, int id){
    to[++ecnt] = v;
    eid[ecnt] = id;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
}
void tarjan(int u, int ine){
    dfn[u] = low[u] = ++idx;
    for(int i = head[u]; i; i = nxt[i]){
        int v = to[i];
        if(!dfn[v]){
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]) isbridge[eid[i]] = true;
        }
        else if(i != (ine ^ 1)){
            low[u] = min(low[u], dfn[v]);
        }
    }
}
void color(int u, int c){
    comp[u] = c;
    for(int i = head[u]; i; i = nxt[i]){
        int v = to[i];
        if(comp[v] || isbridge[eid[i]]) continue;
        color(v, c);
    }
}
int main(){
    int F, R;
    if(!(cin >> F >> R)) return 0;
    for(int i = 0; i < R; i++){
        int a, b;
        cin >> a >> b;
        add(a, b, i);
        add(b, a, i);
    }
    for(int i = 1; i <= F; i++){
        if(!dfn[i]) tarjan(i, 0);
    }
    for(int i = 1; i <= F; i++){
        if(!comp[i]) color(i, ++ccnt);
    }
    for(int i = 2; i <= ecnt; i += 2){
        if(isbridge[eid[i]]){
            deg[comp[to[i]]]++;
            deg[comp[to[i ^ 1]]]++;
        }
    }
    int leaf = 0;
    for(int i = 1; i <= ccnt; i++){
        if(deg[i] == 1) leaf++;
    }
    cout << (leaf + 1) / 2 << "\n";
    return 0;
}
分离的路径

正文

一本通·提高篇的其它内容
