題目
給你一個整數 n ，表示網路上的使用者數目。每個使用者按從 0 到 n - 1 進行編號。
給你一個下標從 0 開始的二維整數陣列 restrictions ，
其中 restrictions［i］ = ［xi， yi］ 意味著使用者 xi 和使用者 yi 不能 成為 朋友 ，不管是 直接 還是透過其他使用者 間接 。
最初，使用者裡沒有人是其他使用者的朋友。給你一個下標從 0 開始的二維整數陣列 requests 表示好友請求的列表，
其中 requests［j］ = ［uj， vj］ 是使用者 uj 和使用者 vj 之間的一條好友請求。
如果 uj 和 vj 可以成為 朋友 ，那麼好友請求將會 成功 。
每個好友請求都會按列表中給出的順序進行處理（即，requests［j］ 會在 requests［j + 1］ 前）。
一旦請求成功，那麼對所有未來的好友請求而言， uj 和 vj 將會 成為直接朋友 。
返回一個 布林陣列 result ，其中元素遵循此規則：如果第 j 個好友請求 成功 ，那麼 result［j］ 就是 true ；否則，為 false 。
注意：如果 uj 和 vj 已經是直接朋友，那麼他們之間的請求將仍然 成功 。
示例 1：輸入：n = 3， restrictions = ［［0，1］］， requests = ［［0，2］，［2，1］］ 輸出：［true，false］
解釋：請求 0 ：使用者 0 和 使用者 2 可以成為朋友，所以他們成為直接朋友。
請求 1 ：使用者 2 和 使用者 1 不能成為朋友，因為這會使 使用者 0 和 使用者 1 成為間接朋友 （1——2——0） 。
示例 2：輸入：n = 3， restrictions = ［［0，1］］， requests = ［［1，2］，［0，2］］ 輸出：［true，false］
解釋：請求 0 ：使用者 1 和 使用者 2 可以成為朋友，所以他們成為直接朋友。
請求 1 ：使用者 0 和 使用者 2 不能成為朋友，因為這會使 使用者 0 和 使用者 1 成為間接朋友 （0——2——1） 。
示例 3：輸入：n = 5， restrictions = ［［0，1］，［1，2］，［2，3］］， requests = ［［0，4］，［1，2］，［3，1］，［3，4］］
輸出：［true，false，true，false］
解釋：請求 0 ：使用者 0 和 使用者 4 可以成為朋友，所以他們成為直接朋友。
請求 1 ：使用者 1 和 使用者 2 不能成為朋友，因為他們之間存在限制。
請求 2 ：使用者 3 和 使用者 1 可以成為朋友，所以他們成為直接朋友。
請求 3 ：使用者 3 和 使用者 4 不能成為朋友，因為這會使 使用者 0 和 使用者 1 成為間接朋友 （0——4——3——1） 。
提示：2 <= n <= 1000
0 <= restrictions。length <= 1000
restrictions［i］。length == 2
0 <= xi， yi <= n - 1
xi ！= yi
1 <= requests。length <= 1000
requests［j］。length == 2
0 <= uj， vj <= n - 1
uj ！= vj
解題思路分析
1、並查集；時間複雜度O（n^2log（n）），空間複雜度O（n）
func friendRequests（n int， restrictions ［］［］int， requests ［］［］int） ［］bool { fa = Init（n） res ：= make（［］bool， len（requests）） for i ：= 0； i < len（requests）； i++ { a， b ：= requests［i］［0］， requests［i］［1］ x， y ：= find（a）， find（b） if x == y { res［i］ = true } else { flag ：= true for j ：= 0； j < len（restrictions）； j++ { // 嘗試每個限制條件 c， d ：= restrictions［j］［0］， restrictions［j］［1］ u， v ：= find（c）， find（d） if （x == u && y == v） || （x == v && y == u） { // 有限制 flag = false break } } if flag == true { res［i］ = true union（x， y） } } } return res}var fa ［］int// 初始化func Init（n int） ［］int { arr ：= make（［］int， n） for i ：= 0； i < n； i++ { arr［i］ = i } return arr}// 查詢func find（x int） int { if fa［x］ ！= x { fa［x］ = find（fa［x］） } return fa［x］}// 合併func union（i， j int） { fa［find（i）］ = find（j）}func query（i， j int） bool { return find（i） == find（j）}
2、並查集；時間複雜度O（n^2log（n）），空間複雜度O（n）
func friendRequests（n int， restrictions ［］［］int， requests ［］［］int） ［］bool { fa = Init（n） res ：= make（［］bool， len（requests）） for i ：= 0； i < len（requests）； i++ { a， b ：= requests［i］［0］， requests［i］［1］ temp ：= make（［］int， n） copy（temp， fa） // 備份當前的結果 union（a， b） // 嘗試連線 flag ：= true for j ：= 0； j < len（restrictions）； j++ { c， d ：= restrictions［j］［0］， restrictions［j］［1］ if query（c， d） == true { // 檢視是否有限制 flag = false break } } if flag == true { res［i］ = true } else { fa = make（［］int， n） // 不滿足條件，恢復回去 copy（fa， temp） } } return res}var fa ［］int// 初始化func Init（n int） ［］int { arr ：= make（［］int， n） for i ：= 0； i < n； i++ { arr［i］ = i } return arr}// 查詢func find（x int） int { if fa［x］ ！= x { fa［x］ = find（fa［x］） } return fa［x］}// 合併func union（i， j int） { fa［find（i）］ = find（j）}func query（i， j int） bool { return find（i） == find（j）}
總結
Hard題目，並查集模板題目
