On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.
Now, a move consists of removing a stone that shares a column or row with another stone on the grid.
What is the largest possible number of moves we can make?
Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Example 3:
Input: stones = [[0,0]] Output: 0
class Solution { public int removeStones(int[][] stones) { if(stones == null || stones.length <= 1) return 0; int n = stones.length; int[] p = new int[n]; for(int i = 0; i < n; i++) p[i] = -1; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]){ union(p, i, j); } } } for(int e : p){ if(e == -1){ n--; } } return n; } private void union(int[] p, int i, int j){ int rooti = find(p, i); int rootj = find(p, j); if(rooti != rootj){ p[rooti] = rootj; } } private int find(int[] p, int i){ if(p[i] == -1) return i; return find(p, p[i]); } }
947. Most Stones Removed with Same Row or Column
原文：https://www.cnblogs.com/tobeabetterpig/p/10296819.html