并查集实现
原理
代码实现
public class UnionFind {
private int size;
private int[] array;
private int[] count;
public UnionFind(int size) {
this.size = size;
array = new int[size];
count = new int[size];
for (int i = 0; i < size; i++) {
array[i] = i;
count[i] = 1;
}
}
public void merge(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
if (count[rootX] >= count[rootY]) {
array[rootY] = rootX;
count[rootX] += count[rootY];
} else {
array[rootX] = rootY;
count[rootY] += count[rootX];
}
size--;
}
public int find(int index) {
while (array[index] != index) {
array[index] = array[array[index]];
index = array[index];
}
return index;
}
public int getSize() {
return size;
}
}
代表题型
leetcode 547 朋友圈
public class UnionFind {
private int size;
private int[] array;
private int[] count;
public UnionFind(int size) {
this.size = size;
array = new int[size];
count = new int[size];
for (int i = 0; i < size; i++) {
array[i] = i;
count[i] = 1;
}
}
public void merge(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
if (count[rootX] >= count[rootY]) {
array[rootY] = rootX;
count[rootX] += count[rootY];
} else {
array[rootX] = rootY;
count[rootY] += count[rootX];
}
size--;
}
public int find(int index) {
while (array[index] != index) {
array[index] = array[array[index]];
index = array[index];
}
return index;
}
public int getSize() {
return size;
}
}
class Solution {
public int findCircleNum(int[][] M) {
int col = M.length;
if (col == 0) {
return 0;
}
UnionFind uf = new UnionFind(col);
for (int i = 0; i < col; i++) {
for (int j = (i + 1); j < col; j++) {
if (M[i][j] == 1) {
uf.merge(i, j);
}
}
}
return uf.getSize();
}
}
leetcode 765 情侣牵手
class UnionFind {
private int size;
private int[] array;
private int[] count;
public UnionFind(int size) {
this.size = size;
count = new int[size];
array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = i;
count[i] = 1;
}
}
public void merge(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
if (count[rootX] >= count[rootY]) {
array[rootY] = rootX;
count[rootX] += count[rootY];
} else {
array[rootX] = rootY;
count[rootY] += count[rootX];
}
size--;
}
public int find(int index) {
while (array[index] != index) {
array[index] = array[array[index]];
index = array[index];
}
return index;
}
public int getSize() {
return size;
}
}
class Solution {
public int minSwapsCouples(int[] row) {
int size = row.length / 2;
UnionFind uf = new UnionFind(size);
for (int i = 0; i < row.length; i = i + 2) {
int val1 = row[i] / 2;
int val2 = row[i + 1] / 2;
uf.merge(val1, val2);
}
return size - uf.getSize();
}
}
leetcode 200 岛屿数量
class UnionFind {
public int getSize() {
return size;
}
private int size;
private int[] count;
private int[] array;
public UnionFind(int size) {
this.size = size;
count = new int[size];
array = new int[size];
for (int i = 0; i < size; i++) {
count[i] = 1;
array[i] = i;
}
}
public void merge(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
if (count[rootX] >= rootY) {
array[rootY] = rootX;
count[rootX] += count[rootY];
} else {
array[rootX] = rootY;
count[rootY] += count[rootX];
}
size--;
return;
}
public int find(int index) {
while (array[index] != index) {
array[index] = array[array[index]];
index = array[index];
}
return index;
}
}
class Solution {
public int numIslands(char[][] grid) {
int row = grid.length;
int col = grid[0].length;
int size = row * col;
UnionFind uf = new UnionFind(size);
int zeroNum = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '0') {
zeroNum++;
} else {
if ((i + 1) < row && grid[i + 1][j] == '1') {
uf.merge(i * col + j, (i + 1) * col + j);
}
if ((j + 1) < col && grid[i][j + 1] == '1') {
uf.merge(i * col + j, i * col + j + 1);
}
}
}
}
return uf.getSize() - zeroNum;
}
}
