ZOJ 3761 Easy Billiards：並查集 + DFS 輸出撞球方案

問題描述

台球桌上有多顆球，座標 (x, y)。若兩球同行（x 相同）或同列（y 相同），可直線撞擊。每次撞擊移除被撞球，撞球者停在目標位置。求：

1. 最少剩餘球數
2. 具體撞擊序列

核心洞察

1. 圖模型與連通分量

• 球 = 頂點
• 同行/同列 = 邊
• 每個連通分量最終至少剩 1 顆球
• 最少剩餘球數 = 連通分量數

2. 並查集求連通分量

將同行/同列的球合併。座標離散化後用鄰接表儲存。

3. DFS 樹構造撞擊方案

• 以每個連通分量的代表元（根）為起點 DFS
• 形成 DFS 樹，葉節點對應可被撞擊的球
• 葉節點撞擊其父節點，一次可移除所有葉子
• 遞迴向上，最終剩根節點

關鍵演算法步驟

1. 輸入與編號：讀入球座標，保留原始索引
2. 排序連接：
   • 按 x 排序，相同 x 連接
   • 按 y 排序，相同 y 連接
3. 並查集合併：統計連通分量數
4. DFS 輸出方案：對每個分量根節點 DFS，記錄撞擊順序

程式碼框架

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN = 10005;

struct Ball {
    int x, y, id;  // 原始編號
} balls[MAXN], tmp[MAXN];

struct Edge {
    int to, next;
} edges[MAXN * 2];
int head[MAXN], ecnt;

int uf[MAXN];  // 並查集

// 並查集查找
int find(int x) {
    return uf[x] == x ? x : uf[x] = find(uf[x]);
}

// 並查集合併
void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a != b) uf[b] = a;
}

// 加邊
void addEdge(int u, int v) {
    edges[ecnt] = {v, head[u]};
    head[u] = ecnt++;
}

// DFS 輸出撞擊序列
bool vis[MAXN];
void dfs(int u, int parent) {
    vis[u] = true;
    for (int e = head[u]; e != -1; e = edges[e].next) {
        int v = edges[e].to;
        if (!vis[v]) dfs(v, u);
    }
    // 後序輸出：葉子先撞父節點
    if (parent != -1) {
        printf("%d %d\n", balls[u].id, balls[parent].id);
    }
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        // 初始化
        ecnt = 0;
        memset(head, -1, sizeof(head));
        for (int i = 1; i <= n; ++i) uf[i] = i;
        
        // 讀入
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &balls[i].x, &balls[i].y);
            balls[i].id = i;
        }
        
        // 按 x 排序連接
        copy(balls+1, balls+n+1, tmp+1);
        sort(tmp+1, tmp+n+1, [](Ball a, Ball b) {
            return a.x != b.x ? a.x < b.x : a.y < b.y;
        });
        for (int i = 2; i <= n; ++i) {
            if (tmp[i].x == tmp[i-1].x) {
                addEdge(tmp[i].id, tmp[i-1].id);
                addEdge(tmp[i-1].id, tmp[i].id);
                unite(tmp[i].id, tmp[i-1].id);
            }
        }
        
        // 按 y 排序連接
        sort(tmp+1, tmp+n+1, [](Ball a, Ball b) {
            return a.y != b.y ? a.y < b.y : a.x < b.x;
        });
        for (int i = 2; i <= n; ++i) {
            if (tmp[i].y == tmp[i-1].y) {
                addEdge(tmp[i].id, tmp[i-1].id);
                addEdge(tmp[i-1].id, tmp[i].id);
                unite(tmp[i].id, tmp[i-1].id);
            }
        }
        
        // 統計連通分量 = 最少剩餘球數
        int components = 0;
        for (int i = 1; i <= n; ++i)
            if (find(i) == i) components++;
        printf("%d\n", components);
        
        // 輸出撞擊方案
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; ++i)
            if (find(i) == i)
                dfs(i, -1);
    }
    return 0;
}

關鍵技術點

1. 離散化與鄰接表

座標範圍大但球數少（≤10000），用結構體保留 id 映射回原始編號。

2. 並查集路徑壓縮

int find(int x) {
    return uf[x] == x ? x : uf[x] = find(uf[x]);
}

近乎 O(1) 摊還複雜度。

3. DFS 後序輸出策略

• 先遞迴處理子樹
• 返回時輸出「當前節點撞擊父節點」
• 葉節點最先輸出，符合「可被撞擊」條件
• 根節點無父節點，不輸出（最終剩餘）

複雜度分析

• 排序：O(n log n) × 2
• 並查集：O(n α(n))
• DFS：O(n + m)，m 為邊數 ≤ 2n
• 總體：O(n log n)

常見坑點

1. 同座標多球：需正確連接（排序後相鄰判斷自動處理）
2. 輸出格式：每行一對 撞擊球 目標球
3. 遞迴深度：n ≤ 10000 可能棧溢出，可改用迭代 DFS 或增大棧

總結

ZOJ 3761 巧妙結合並查集統計最優解與DFS 構造可行方案。核心洞見：連通分量數 = 最少剩餘球，DFS 樹後序遍歷 = 合法撞擊序列。此類「求最優值 + 輸出方案」雙重要求題目，常用「圖論結構分析 + 遍歷輸出」雙階段解題模式。