誰もがC++で友達になった最初の瞬間

ソーシャルグループに、0からN-1までの一意の整数IDを持つN人の異なる人々がいるとします。ここにログのリストがあります。各logs[i]=[time、id_A、id_B]には、負でない整数のタイムスタンプと2人の異なる人物のIDが含まれています。各ログには、2人の異なる人が友達になった時間が示されています。 AがBと友達である場合、BはAと友達です。AがBと友達である場合、またはAがBと知り合いである場合、AはBと知り合いであるとしましょう。すべての人が他のすべての人と知り合いになりました。そのような時間が見つからない場合は、-1を返します。したがって、入力が次のようになっている場合：[[20190101,0,1]、[20190104,3,4]、[20190107,2,3]、[20190211,1,5] 、[20190224,2,4]、[20190301,0,3]、[20190312,1,2]、[20190322,4,5]]、N =6、出力は20190301になります。これは、最初のイベントが発生するためです。タイムスタンプ=20190101で、人0と1が友達になった後、友情グループ[0,1]、[2]、[3]、[4]、[5]があります。次に、2番目のイベントがタイムスタンプ=20190104で発生し、人3と4が友達になった後、次の友情グループ[0,1]、[2]、[3,4]、[5]があります。その後、3番目のイベントはタイムスタンプ=20190107で発生し、人物2と3が友達になった後、次の友情グループ[0,1]、[2,3,4]、[5]があります。次に、4番目のイベントがタイムスタンプ=20190211で発生し、人1と5が友達になった後、次の友情グループ[0,1,5]、[2,3,4]があります。その後、タイムスタンプ=20190224で5番目のイベントが発生し、人2と4はすでに友達であるため、何かが起こります。最後に、6番目のイベントはタイムスタンプ=20190301で発生し、人0と3が友達になった後、全員が友達になります。

これを解決するには、次の手順に従います-

• find（）というメソッドを定義します。これは値xを取り、次のように機能します-

• 親[x]が-1の場合、x

  を返します

• 親[x]：=find（親[x]）

• 親を返す[x]

• mainメソッドでは、次のように機能します-

• サイズNの親とランクと呼ばれる2つの配列を定義し、親を-1で埋め、ランクを1で埋めます

• ログを並べ替える

• ログ内の各要素iについて-

  • i[1]とi[2]

    で結合を実行します

  • find（i [2]）およびfind（i [1]）

  • Nがランク配列にある場合は、i [0]

    を返します。

• -1を返す

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int earliestAcq(vector<vector<int>>& logs, int N) {
      vector<int> ds (N, -1);
      sort(begin(logs), end(logs));
      for(vector<int> &k : logs) {
         if(un(k[1], k[2], ds) == N) return k[0];
      }
      return -1;
   }
   int un(int u, int v, vector<int> & ds) {
      u = find(u, ds);
      v = find(v, ds);
      if(u != v) {
         ds[v] += ds[u];
         ds[u] = v;
      }
      return -ds[v];
   }
   int find(int u, vector<int> & ds) {
      return ds[u] < 0? u : ds[u] = find(ds[u], ds);
   }
};
main(){
   vector<vector<int>> v = {
      {20190101,0,1},{20190104,3,4},{20190107,2,3},{20190211,1,5},
      {20190224,2,4},{20190301,0,3},{20190312,1,2},{20190322,4,5}
   };
   Solution ob;
   cout <<ob.earliestAcq(v, 6);
}

入力

[[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],
[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]]
6

出力

20190301