Luogu 🟢 P1955 [NOI2015] 程序自动分析

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P1955 [NOI2015] 程序自动分析

Problem Statement

題目簡述

有若干個以整數編號的變數 $x_1,x_2,\ldots$。
給定 $n$ 條形如 $(i, j, e)$ 的約束：

• $e = 0$ 表示 $x_i = x_j$
• $e = 1$ 表示 $x_i \ne x_j$

請判斷是否存在某種賦值，使得所有約束能同時成立。

Constraints

約束條件

• $1 \le t \le 10$
• $1 \le n \le 10^5$
• $1 \le i, j \le 10^9$
• $e \in \{0, 1\}$

---

思路：離散化 + 併查集

方法一：離線作法，先合併相等再檢查不等

把「相等」視為同一個集合、把「不等」視為集合之間不能相同。

關鍵是：若兩個變數必須相等，那它們在任何可行賦值下都一定屬於同一集合；因此可以先把所有相等關係用併查集合併，最後只要檢查每條不等關係是否落在不同群集合。

但題目中的變數編號最大到 $10^9$，不能直接拿原編號當陣列下標，所以要先做離散化：把本測資出現過的所有編號蒐集起來、排序後映射成 $0\ldots m-1$。

為什麼一定要「先相等後不等」？

因為相等會把多個點收縮成同一個代表元，不等的判定必須在收縮之後才準確；反過來做會漏掉「經由相等推出」的矛盾。

複雜度分析

• 時間複雜度：$\mathcal{O}(m\log m + n\,\alpha(m))$，其中 $m$ 是離散化後的不同變數數量（$m \le 2n$），
  • 每組測資離散化排序 $\mathcal{O}(m\log m)$
  • 併查集合併/查找攤還 $\mathcal{O}(n\,\alpha(m))$
• 空間複雜度：$\mathcal{O}(m+n)$（映射、併查集與約束存放）

方法二：偽在線作法，啟發式合併

如果將題目修改成，當遇到每條約束時就要立即判定是否矛盾（但在發生矛盾時忽略該約束繼續處理後續約束），該怎麼做？

這個要求讓方法一的離線作法不再適用，因為它必須先把所有相等約束合併完才能檢查不等約束；如果要在線處理，就必須在每次合併時同時檢查是否與既有的不等約束衝突。

注意到這本質上仍是集合合併的問題，但我們可以額外維護一個「不等集合」：對每個集合的代表元，記錄那些必須與它不同的節點。每次合併兩個集合前，先檢查其中一個集合的不等集合裡是否有任何節點屬於另一個集合；如果有，就會形成「同群但又必不同」的矛盾；若沒發生矛盾，才把兩個集合合併，並把它們的不等集合合併在一起。

但這裡有個問題是，如果不等集合裡的節點很多，檢查時可能會很慢；因此可以採用啟發式合併，讓每次合併都把較小的不等集合併入較大的，並檢查較小的集合，來降低總搬移成本。

為什麼稱作「偽在線」？

因為本題中的節點編號很大，仍然需要先離散化才能使用併查集；離散化本身就是一個離線步驟，因此整體流程仍然不是完全在線的。但若題目的編號範圍較小，或是改成直接給出離散化後的編號，就可以真正在線處理。

複雜度分析

• 時間複雜度：$\mathcal{O}(m\log m)$，其中 $m$ 是離散化後的不同變數數量（$m \le 2n$），
  • 離散化排序 $\mathcal{O}(m\log m)$
  • 啟發式合併均攤後為 $\mathcal{O}(m\log m)$
• 空間複雜度：$\mathcal{O}(m+n)$
  • 併查集需要 $\mathcal{O}(m)$ 空間（代表元與大小陣列）
  • 不等集合總元素數量最多為 $2n$（每條不等約束最多會在兩個集合中各加入一個元素），且合併後會刪除較小的集合，因此需要 $\mathcal{O}(n)$ 空間

啟發式合併的複雜度分析

啟發式合併的核心思想是每次合併都將較小的集合併入較大的集合，這樣可以確保每個元素在被併入其他集合的過程中，最多只會被移動 $\mathcal{O}(\log m)$ 次（因為每次合併至少會將集合大小翻倍）。因此，對於 $m$ 個元素，總的搬移成本為 $\mathcal{O}(m \log m)$。

---

Code

方法一：離線作法，離散化 + 併查集

class UnionFind:
    __slots__ = ["n", "pa", "sz", "cnt"]

    def __init__(self, n: int):
        self.n = n
        self.pa = list(range(n))  # 父節點
        self.sz = [1] * n  # 連通分量大小
        self.cnt = n  # 連通分量數量

    def find(self, x: int) -> int:
        """Iterative version, path halving"""
        while self.pa[x] != x:
            self.pa[x] = self.pa[self.pa[x]]
            x = self.pa[x]
        return x

    def union(self, x: int, y: int) -> bool:
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return False
        if self.sz[fx] < self.sz[fy]:
            fx, fy = fy, fx
        self.pa[fy] = fx
        self.sz[fx] += self.sz[fy]
        self.cnt -= 1
        return True


def solve():
    n = int(input())
    Xs = set()
    constraints = [[] for _ in range(2)]
    for _ in range(n):
        a, b, e = map(int, input().split())
        constraints[e].append((a, b))
        Xs.add(a)
        Xs.add(b)

    Xs = sorted(Xs)
    mp = {x: i for i, x in enumerate(Xs)}
    m = len(Xs)

    uf = UnionFind(m)
    for a, b in constraints[1]:
        uf.union(mp[a], mp[b])
    for a, b in constraints[0]:
        if uf.find(mp[a]) == uf.find(mp[b]):
            print("NO")
            break
    else:
        print("YES")


if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

方法二：偽在線作法，啟發式合併

def solve():
    n = int(input())
    Xs = set()
    constraints = []
    for _ in range(n):
        a, b, e = map(int, input().split())
        constraints.append((a, b, e))
        Xs.add(a)
        Xs.add(b)

    Xs = sorted(Xs)
    mp = {x: i for i, x in enumerate(Xs)}
    m = len(Xs)

    fa = list(range(m))  # 父節點
    diffs = [set() for _ in range(m)]  # diffs[u] 表示與需與 u 不同的節點集合

    def find(x):
        while fa[x] != x:
            fa[x] = fa[fa[x]]
            x = fa[x]
        return x

    for a, b, e in constraints:
        x, y = mp[a], mp[b]
        fx, fy = find(x), find(y)
        if e == 1:  # 相等關係
            if fx == fy:
                continue
            # 啟發式合併，讓 fy 是較小的集合
            if len(diffs[fx]) < len(diffs[fy]):
                fx, fy = fy, fx
            if any(find(u) == fx for u in diffs[fy]):
                print("NO")
                break
            fa[fy] = fx
            diffs[fx].update(diffs[fy])
            diffs[fy].clear()
        else:  # 相異關係
            if fx == fy:
                print("NO")
                break
            diffs[fx].add(y)
            diffs[fy].add(x)
    else:
        print("YES")