題目

我們將石頭放置在二維平面中的一些整數座標點上。每個座標點上最多隻能有一塊石頭。

每次 move 操作都會移除一塊所在行或者列上有其他石頭存在的石頭。

請你設計一個演算法，計算最多能執行多少次 move 操作？

示例 1：輸入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] 輸出：5

示例 2：輸入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] 輸出：3

示例 3：輸入：stones = [[0,0]] 輸出：0

提示：1 <= stones.length <= 1000

0 <= stones[i][j] < 10000

1、並查集；時間複雜度O(n)，空間複雜度O(n)

func removeStones(stones [][]int) int {	fa := make([]int, 20000)	for i := 0; i < 20000; i++ {		fa[i] = i	}	for i := 0; i < len(stones); i++ {		a, b := stones[i][0], stones[i][1]		// 連線同一行、列		union(fa, a, b+10000)	}	m := make(map[int]bool)	for i := 0; i < len(stones); i++ {		a := stones[i][0]		m[find(fa, a)] = true	}	return len(stones) - len(m)}func union(fa []int, a, b int) {	fa[find(fa, a)] = find(fa, b)}func find(fa []int, a int) int {	for fa[a] != a {		fa[a] = fa[fa[a]]		a = fa[a]	}	return a}

2、深度優先搜尋；時間複雜度O(n^2)，空間複雜度O(n^2)

var arr [][]intvar m []boolfunc removeStones(stones [][]int) int {	n := len(stones)	arr = make([][]int, n)	for i := 0; i < n; i++ {		arr[i] = make([]int, 0)	}	for i := 0; i < n; i++ {		for j := i + 1; j < n; j++ {			if stones[i][0] == stones[j][0] || // 同行				stones[i][1] == stones[j][1] { // 同列				arr[i] = append(arr[i], j)				arr[j] = append(arr[j], i)			}		}	}	m = make([]bool, n)	count := 0	for i := 0; i < n; i++ {		count = count + dfs(i)	}	return len(stones) - count}func dfs(index int) int {	if m[index] == true {		return 0	}	m[index] = true	for i := 0; i < len(arr[index]); i++ {		dfs(arr[index][i])	}	return 1}

Medium題目，使用並查集能組成多少個獨立的行和列，最後總數減去即可