---
title: "AtCoder Beginner Contest 238 E(並查集)"
tags: 題解, 資料結構, 並查集
---

https://atcoder.jp/contests/abc238/tasks/abc238_e

#### 題意

有一個長度 $N$ 的數組 $a_1, a_2, ..., a_N$，已知你可以得到 $Q$ 個區間的和，問是否能知道整個數組的和。

#### 思路

對於一個區間 $[L, R]$，如果我們得到 $pref[L - 1]$，則透過 $[L, R]$ 和 $pref[L - 1]$ 可以得到 $pref[R]$；同理，得到 $pref[R]$ 的話也可以得到 $pref[L - 1]$。因此，對於 $[L, R]$，得知 $pref[L - 1]$ 相當於得知 $pref[R]$，反之亦然。

我們處理每個區間時，將 $[L, R]$ 中的 $L - 1$ 和 $R$ 合併起來；最後看一下 $0$ 和 $N$ 是否有被合併起來即可，透過並查集可以做到。

#### Code

def solve():
    N, Q = map(int, input().split())

    dsu = DSU(N + 1)
    for _ in range(Q):
        l, r = map(int, input().split())
        dsu.union(l - 1, r)
    print("Yes" if dsu.same(0, N) else "No")

if __name__ == "__main__":
    solve()