一個難度很大的程序

Question

這是我在csstack交換中的第一篇文章，我不知道這類問題是否可以在這裏發佈。

所以我一直在嘗試這個問題3天，我得到了一個解決方案，但它的隱藏測試用例失敗。

問：

有一個村莊的節日發生在幾個組的親戚每年召開一次會議。每個人都被分配了一個正整數的標識符.N對親屬標識符作爲輸入被傳遞。

然後終於給一個人的識別碼I，程序必須與標識打印親屬C的計數組的人在一

輸入格式： 第一行包含N的值N行包含兩個相關人員的標識符。 下一行（N + 2）行將包含要打印其組的相對計數的人員的標識符I.

輸出格式： 第一行將包含親屬C的計數的組的人的與標識符I.

邊界條件： = N < = 100001 < = I < = 1000000

例 輸入/輸出1： 輸入：

5 
10 20 
30 20 
40 10 
55 35 
55 22 
40 

輸出：4

說明：

10，20，30，40形成的相對基。 55,35,22形成另一個相對組。 因此，與標識符40親屬的人的數量是4

我走近的方法是：

for(auto i = v.begin() ; i!=v.end();i++) 
{ 
    if(i->first == r || i->second == r) 
     { 
      count+=2; 
      if(i->first == r) 
      r = i->second; 
      else 
      r = i->first; 
      remove(v.begin(),v.end(),*i); 
      n--; 
      break; 
     } 
} 

for(int i =0;i<n;i++) 
{ 
    for(int j =0;j<n;j++) 
    { 
     if(r == v[j].first || r == v[j].second) 
      { 
       if(r == v[j].first) 
        r = v[j].second; 
       else 
        r = v[j].first; 

       count++; 
       remove(v.begin(),v.end(),v[j]); 
       n--; 
      } 
    } 
} 

cout<<count; 

那麼什麼是正確的解決這個問題？

Answer 1

本質上，你的問題是這樣的： 給出表示爲指數和邊緣作爲指數對， 節點的圖和一個給定的索引i表示的節點， 找到它們被連接到給定節點的所有節點。

UnionFind算法找到了節點連接的組件與指數：

Initialize an array father of size number of nodes, with father[i] = i 

for each edge e consisting of two indices i, j: 
    ind = i 
    while(ind != father[ind]) ind = father[ind] 
    father[j] = ind 

for each entry i of the array: 
    replace father[i] by father[father[i]] until those are equal 

之後，在相同的組件中的所有節點都具有相同的父親。你用你的數據做這件事，然後，對於一個給定的索引i，用父親[i] = father [j]找到所有其他指數j。

（在運行時間略有好轉：IND後設置爲它的終值，更新父親我和父親等方面的價值IND）

UnionFind的簡短解釋：它創建了一個樹只存儲索引到節點父親的指針（只需要一個數組）。這是通過遍歷邊來完成的。對於每個邊，其中一個事件節點的父親被設置爲另一個節點的最高祖先。本質上，我們從單個節點的森林開始，並將它們組裝到樹中。最後，我們改變剩餘的樹木，讓所有的樹葉都是根的直接子代。

由於在您的示例中缺少一些數字，因此您可能需要創建一些表，將輸入索引轉換爲實際使用的數字範圍。但是，如果我們談論的是一個小的最大指數，比如低於1000，那麼不會真的傷害不這樣做。