1101-TheEarliestMomentWhenEveryoneBecomeFriends.go

package main

// 1101. The Earliest Moment When Everyone Become Friends
// There are n people in a social group labeled from 0 to n - 1. 
// You are given an array logs where logs[i] = [timestampi, xi, yi] indicates that xi and yi will be friends at the time timestampi.

// Friendship is symmetric. That means if a is friends with b, then b is friends with a. 
// Also, person a is acquainted with a person b if a is friends with b, or a is a friend of someone acquainted with b.

// Return the earliest time for which every person became acquainted with every other person. 
// If there is no such earliest time, return -1.

// Example 1:
// Input: logs = [[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
// Output: 20190301
// Explanation: 
// The first event occurs at timestamp = 20190101, and after 0 and 1 become friends, we have the following friendship groups [0,1], [2], [3], [4], [5].
// The second event occurs at timestamp = 20190104, and after 3 and 4 become friends, we have the following friendship groups [0,1], [2], [3,4], [5].
// The third event occurs at timestamp = 20190107, and after 2 and 3 become friends, we have the following friendship groups [0,1], [2,3,4], [5].
// The fourth event occurs at timestamp = 20190211, and after 1 and 5 become friends, we have the following friendship groups [0,1,5], [2,3,4].
// The fifth event occurs at timestamp = 20190224, and as 2 and 4 are already friends, nothing happens.
// The sixth event occurs at timestamp = 20190301, and after 0 and 3 become friends, we all become friends.

// Example 2:
// Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
// Output: 3
// Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.
 
// Constraints:
//     2 <= n <= 100
//     1 <= logs.length <= 10^4
//     logs[i].length == 3
//     0 <= timestampi <= 10^9
//     0 <= xi, yi <= n - 1
//     xi != yi
//     All the values timestampi are unique.
//     All the pairs (xi, yi) occur at most one time in the input.

import "fmt"
import "sort"

func earliestAcq(logs [][]int, n int) int {
    parent, count := make([]int,n), make([]int,n)
    for i := 0; i < n; i++ {
        parent[i], count[i] = i, 1
    }
    var find func(int) int
    find = func(x int) int{
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    sort.Slice(logs,func(i,j int) bool{
        return logs[i][0] < logs[j][0]
    })
    for _, log := range logs {
        t, i, j := log[0], log[1], log[2]
        if i > j { // swap
            i, j = j, i
        }
        t1, t2 := find(i), find(j)
        if t1 != t2 {
            parent[t2] = t1
            count[t1] += count[t2]
        }
        if count[t1] == n {
            return t
        }
    }
    return -1
}

func earliestAcq1(logs [][]int, n int) int {
    uf := NewUnionFind(n)
    sort.Slice(logs, func(i, j int) bool {
        return logs[i][0] < logs[j][0]
    })
    for _, log := range logs {
        t, i, j := log[0], log[1], log[2]
        uf.Union(i, j)
        if uf.count == 1 {
            return t
        }
    }
    return -1
}

type UnionFind struct {
    parents []int
    ranks   []int
    count int
}

func NewUnionFind(n int) *UnionFind {
    parents, ranks := make([]int, n), make([]int, n)
    for i := range parents {
        parents[i] = i
    }
    return &UnionFind{ parents, ranks, n }
}

func (this *UnionFind) Find(x int) int {
    if this.parents[x] != x {
        this.parents[x] = this.Find(this.parents[x]) // 路径压缩
    }
    return this.parents[x]
}

func (this *UnionFind) Union(x, y int) {
    xroot, yroot := this.Find(x), this.Find(y)
    if xroot == yroot {
        return
    }
    xrank, yrank := this.ranks[x], this.ranks[y]
    if xrank < yrank {
        this.parents[xroot] = yroot
    } else if xrank < yrank {
        this.parents[yrank] = yroot
    } else {
        this.parents[yroot] = xroot
        this.ranks[xroot]++
    }
    this.count--
}

func main() {
    // Example 1:
    // Input: logs = [[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
    // Output: 20190301
    // Explanation: 
    // The first event occurs at timestamp = 20190101, and after 0 and 1 become friends, we have the following friendship groups [0,1], [2], [3], [4], [5].
    // The second event occurs at timestamp = 20190104, and after 3 and 4 become friends, we have the following friendship groups [0,1], [2], [3,4], [5].
    // The third event occurs at timestamp = 20190107, and after 2 and 3 become friends, we have the following friendship groups [0,1], [2,3,4], [5].
    // The fourth event occurs at timestamp = 20190211, and after 1 and 5 become friends, we have the following friendship groups [0,1,5], [2,3,4].
    // The fifth event occurs at timestamp = 20190224, and as 2 and 4 are already friends, nothing happens.
    // The sixth event occurs at timestamp = 20190301, and after 0 and 3 become friends, we all become friends.
    logs1 := [][]int{{20190101,0,1},{20190104,3,4},{20190107,2,3},{20190211,1,5},{20190224,2,4},{20190301,0,3},{20190312,1,2},{20190322,4,5}}
    fmt.Println(earliestAcq(logs1, 6)) // 20190301
    // Example 2:
    // Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
    // Output: 3
    // Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.
    logs2 := [][]int{{0,2,0},{1,0,1},{3,0,3},{4,1,2},{7,3,1}}
    fmt.Println(earliestAcq(logs2, 4)) // 3

    fmt.Println(earliestAcq1(logs1, 6)) // 20190301
    fmt.Println(earliestAcq1(logs2, 4)) // 3
}