🔗 UVA-12428 Enemy at the Gates

tags: `貪婪(Greedy)`, `二分搜尋(Binary Search)`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。
python 可以於 UVA 和 瘋狂程設(CPE) 上直接通過；但於 ZeroJudge 上需要加上二分搜尋(Binary Search) 的技巧才能通過。

題意

給定一個具有 $m$ 條邊、 $n$ 個點的簡單無向連通圖。
如果刪除一條邊後，會使得圖中的某些點無法連通，則這條邊被認為是重要/關鍵的，求給定的圖中最多有幾條這種邊？

思路：貪婪(Greedy) + 暴力枚舉(Brute Force) / 二分搜尋(Binary Search)

首先來看只有一個關鍵邊的情況，如範例一的 $(1, 4)$ ，此時該條邊連接了一個孤立點和其餘點的連通分量。
為使這種關鍵邊越多，我們可以將每條關鍵邊都視為一個孤立點和其餘點的連通分量連接，如範例二中可以視為 $3$ 個孤立點和 $1$ 個連通分量的連接。
但此時有個問題，若存在 $k$ 個關鍵邊，則代表存在 $k$ 個孤立點，且由於原圖是連通的，因此剩下 $n-k$ 個點要構成連通分量。為方便說明，以下令 $x = n-k$ 。
由於給定的圖必須是簡單圖，不能存在重複的邊，因此這個連通分量中最多只能有 $\frac{x \times (x-1)}{2}$ 條邊，因此若剩餘的邊數 $m-k \leq \frac{x \times (x-1)}{2}$ ，則代表可以存在 $k$ 個關鍵邊，反之則無法存在 $k$ 個關鍵邊。

解法一：貪婪(Greedy) + 暴力枚舉(Brute Force)

由於目標是找到最多的關鍵邊，因此我們可以從 $k = n-1$ $k = n - 1$ 開始枚舉，直到找到最大的 $k$ $k$ 使得 $\frac{x \times (x-1)}{2} \geq m-k$ $\frac{x \times ( x - 1 )}{2} \geq m - k$ 即可。
- 在枚舉 $k$ 時有個小地方要注意，關鍵邊的數量最多是 $n-1$ 條，而不是 $n$ 條，可以自行思考為什麼。
時間複雜度： $O(n)$ ，對於每個詢問。
空間複雜度： $O(1)$ 。

T = int(input())

for _ in range(T):
    n, m = map(int, input().split()) # n vertices, m edges
    for k in range(n-1, -1, -1): # 枚舉關鍵點的數量 k ，從 n-1 開始
        x = n - k # 剩餘x個點，是否可以構成連通分量
        # k條邊使k個關鍵點連接到該強連通分量，剩餘 m-k 邊皆屬於該強連通分量，該強連通分量最多可以有 x*(x-1)/2 條邊
        if x * (x-1) // 2 >= m - k:
            print(k)
            break

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    LL t, n, m;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (LL k = n-1; k >= 0; --k) {
            LL x = n - k;
            if (x * (x-1) / 2 >= m - k) {
                cout << k << endl;
                break;
            }
        }
    }
    return 0;
}

解法二：貪婪(Greedy) + 二分搜尋(Binary Search)

由於 UVA 和 ZeroJudge 上使用的是相對較舊的 Python 版本，其中的 bisect 套件並不支持自訂 key function，因此需要自行實作二分搜尋(Binary Search)的過程。

將上述的暴力枚舉上傳到 ZeroJudge 後，會發現使用 Python 的程式碼會超時，因此我們需要使用二分搜尋(Binary Search)的技巧來加速。
要二分必須滿足單調性質，而上述暴力枚舉中的檢查條件 $\frac{x \times (x-1)}{2} \geq m - k$ 就是單調的，因此我們可以將其視為一個單調函數，進行二分搜尋。
二分是紅藍染色，而這裡的單調性質是從 $True$ (紅色) 到 $False$ (藍色) ，而閉區間 $[left, right]$ 的二分搜尋，最後的 $right$ 會是最後一個紅色、 $left$ 會是第一個藍色。由於我們要求的是最多的關鍵邊，因此最後的答案就是 $right$ 。
時間複雜度： $O(\log n)$ ，對於每個詢問。
空間複雜度： $O(1)$ 。

def check(k):
    x = n - k
    return x * (x-1) // 2 >= m - k

T = int(input())
for _ in range(T):
    n, m = map(int, input().split()) # n vertices, m edges
    left, right = 0, n-1 # [0, n-1]
    while left <= right:
        mid = (left + right) // 2
        if check(mid):
            left = mid + 1
        else:
            right = mid - 1
    print(right)

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    LL t, n, m;
    cin >> t;
    while (t--) {
        LL n, m, x, k;
        cin >> n >> m;
        LL left = 0, right = n-1;
        while (left <= right) {
            k = (left + right) / 2; // mid
            x = n - k;
            if (x * (x-1) / 2 >= m - k) left = k + 1;
            else right = k - 1;
        }
        cout << right << endl;
    }
    return 0;
}