CSES Chess Tournament 題解與證明

題目

https://cses.fi/problemset/task/1697/

演算法

不斷選取目前度數最大的點

S

，假設度數為

s

，與除了

S

以外度數前

s

大的人建邊，並繼續做下去直到所有人的度數都為

0

，代表可以成功建圖。若演算法執行過程中發現有某個

S

無法和度數前

s

大的人建邊（例如：剩下的人不夠多），代表這不是合法的度序列。

正確性證明

假設

A = {s, t_{1}, t_{2}, \dots, t_{s}, d_{1}, d_{2}, \dots, d_{n}}

是一個非嚴格遞減的序列，

A^{'} = {t_{1} - 1, t_{2} - 1, \dots t_{s} - 1, d_{1}, d_{2}, \dots d_{n}}

是一個度序列。

對

A

來說可以對應到一個圖

G

有點集

{S, T_{1}, T_{2}, \dots, T_{s}, D_{1}, D_{2}, \dots, D_{n}}

，但我們尚不知道

S

與其他點的相鄰情況，假設目前有兩種情況：

Case 1

S

與

T_{1}, T_{2}, \dots, T_{s}

相鄰。此時將

G

刪去

S

的新圖度序列就是

A^{'}

。若

A^{'}

可以構成簡單圖，則

A

顯然也能構成簡單圖。

Case 2

S

至少與

D_{x} (1 \leq x \leq n)

其中一個點相連，這代表存在一個

T_{y} (1 \leq y \leq s)

使得

S

與

T_{x}

不相鄰。根據前提我們可知

t_{y} \geq d_{x}

，我們再分兩個情況討論：

Case 2-1

t_{y} = d_{x}

。我們可以將

T_{y}

與

D_{x}

交換，這樣不會使得

A

改變。

Case 2-2

t_{y} > d_{x}

。這代表存在一個點

W

使得

W

與

T_{y}

相鄰，但

W

與

D_{x}

不相鄰。這樣我們可以把邊

S D_{x}

、

W T_{y}

刪除，加上邊

S T_{y}

、

W D_{x}

，這樣不會使得

A

改變。

由上可知

S

只要與任何一個非

T_{1}, T_{2}, \dots T_{s}

的點相鄰，則我們總有一個交換的方法使得讓

S

多和

T_{1}, T_{2}, \dots T_{s}

其中一點相鄰，會到 Case 1。最終，

A

是否為合法度序列就由

A^{'}

決定，可以遞迴下去地做。

參考資料