Giả sử trong một nhóm xã hội, có N người khác nhau, với id số nguyên duy nhất từ 0 đến N-1. Ở đây chúng tôi có một danh sách các nhật ký, trong đó mỗi nhật ký [i] =[time, id_A, id_B] chứa một dấu thời gian số nguyên không âm và id của hai người khác nhau. Mỗi nhật ký hiển thị thời gian mà hai người khác nhau đã trở thành bạn của nhau. Nếu A là bạn với B thì B là bạn với A. Giả sử người A quen với người B nếu A là bạn với B, hoặc A là bạn của người quen B. Ta phải tìm thời gian sớm nhất cho mà mọi người đã trở nên quen thuộc với mọi người khác. Nếu không tìm thấy thời gian như vậy, thì trả về -1 Vì vậy, nếu đầu vào là:[[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, Đầu ra sẽ là 20190301. Điều này là do sự kiện đầu tiên xảy ra tại dấu thời gian =20190101 và sau khi người 0 và 1 trở thành bạn, chúng ta có các nhóm tình bạn [0,1], [2], [3], [4], [5]. Sau đó sự kiện thứ hai xảy ra tại timestamp =20190104 và sau khi người 3 và 4 trở thành bạn thì chúng ta có các nhóm tình bạn sau [0,1], [2], [3,4], [5]. Sau đó sự kiện thứ ba xảy ra tại timestamp =20190107 và sau khi người 2 và người 3 trở thành bạn thì chúng ta có các nhóm tình bạn sau [0,1], [2,3,4], [5]. Sau đó, sự kiện thứ tư xảy ra tại dấu thời gian =20190211 và sau khi người 1 và người 5 trở thành bạn, chúng ta có các nhóm tình bạn sau [0,1,5], [2,3,4]. Ở đó, sau khi sự kiện thứ năm xảy ra tại dấu thời gian =20190224 và vì người 2 và 4 đã là bạn nên mọi chuyện sẽ xảy ra. Cuối cùng, sự kiện thứ sáu xảy ra tại timestamp =20190301 và sau khi người 0 và 3 trở thành bạn, chúng ta có tất cả những người đó trở thành bạn.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một phương thức được gọi là find (), phương thức này sẽ nhận giá trị x, điều này sẽ hoạt động như sau -
-
nếu cha mẹ [x] là -1, thì trả về x
-
cha mẹ [x]:=find (cha mẹ [x])
-
trả lại cha mẹ [x]
-
Trong phương thức chính, nó sẽ hoạt động như sau -
-
Xác định hai mảng được gọi là cha mẹ và xếp hạng, có kích thước N, điền cha mẹ bằng -1 và điền thứ hạng bằng 1s
-
sắp xếp nhật ký
-
cho mỗi phần tử tôi trong nhật ký -
-
thực hiện liên kết trên tôi [1] và tôi [2]
-
find (i [2]) và find (i [1])
-
nếu N nằm trong mảng xếp hạng, thì trả về i [0]
-
-
trả về -1
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
#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);
} Đầu vào
[[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
Đầu ra
20190301