C++에서 모두가 친구가 되는 가장 빠른 순간

한 사회 집단에 0에서 N-1까지의 고유 정수 ID를 가진 N명의 다른 사람들이 있다고 가정합니다. 여기에 로그 목록이 있습니다. 여기서 각 logs[i] =[time, id_A, id_B]에는 음수가 아닌 정수 타임스탬프와 서로 다른 두 사람의 ID가 포함됩니다. 각 로그는 서로 다른 두 사람이 친구가 된 시간을 보여줍니다. 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이 됩니다. 첫 번째 이벤트가 발생하기 때문입니다. timestamp =20190101이고 사람 0과 1이 친구가 된 후 친구 그룹 [0,1], [2], [3], [4], [5]가 있습니다. 그런 다음 두 번째 이벤트는 타임스탬프 =20190104에서 발생하고 사람 3과 4가 친구가 된 후 다음과 같은 우정 그룹 [0,1], [2], [3,4], [5]이 있습니다. 그 후 세 번째 이벤트는 타임스탬프 =20190107에서 발생하고 사람 2와 3이 친구가 된 후 다음과 같은 친구 그룹 [0,1], [2,3,4], [5]이 있습니다. 그런 다음 네 번째 이벤트는 timestamp =20190211에서 발생하고 사람 1과 5가 친구가 된 후 다음과 같은 우정 그룹 [0,1,5], [2,3,4]이 있습니다. 타임스탬프 =20190224에서 다섯 번째 이벤트가 발생한 후 사람 2와 4가 이미 친구이므로 모든 일이 발생합니다. 마지막으로 여섯 번째 이벤트는 timestamp =20190301에서 발생하며 사람 0과 3이 친구가 된 후 모두 친구가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• find()라는 메서드를 정의하면 값 x가 사용되며 다음과 같이 작동합니다. -

• 부모[x]가 -1이면 x를 반환합니다.

• 부모[x] :=찾기(부모[x])

• 부모 반환[x]

• 기본 방법에서는 다음과 같이 작동합니다 -

• 크기가 N이고 상위 항목을 -1로 채우고 순위를 1로 채우는 상위 및 순위라는 두 개의 배열을 정의합니다.

• 로그 정렬

• 로그의 각 요소 i에 대해 -

  • i[1] 및 i[2]에서 합집합 수행

  • 찾기(i[2]) 및 찾기(i[1])

  • N이 순위 배열에 있으면 i[0]

    를 반환합니다.

• 반환 -1

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include 네임스페이스 std;class Solution { public:int earlyAcq(vector>&logs, int N) { vector ds (N, -1); 정렬(시작(로그), 끝(로그)); for(vector &k :로그) { if(un(k[1], k[2], ds) ==N) return k[0]; } 리턴 -1; } int un(int u, int v, vector &ds) { u =find(u, ds); v =찾기(v, ds); if(u !=v) { ds[v] +=ds[u]; ds[u] =v; } 반환 -ds[v]; } int find(int u, vector &ds) { return ds[u] <0? 유 :ds[u] =찾기(ds[u], ds); }};main(){ 벡터<벡터> 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}}; 솔루션 ob; cout < 
입력
 <미리>[[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