并查集模版(Java)
import java.util.Scanner;
public class UnionFind {
public static int[] parent;
//获得该集合的老大,带路径压缩
public static int get_boss(int v) {
if (parent[v] == v)
return v;
else {
parent[v] = get_boss(parent[v]);
return parent[v];
}
}
//合并两个集合
public static void Merge(int v, int u) {
int t1 = get_boss(v);
int t2 = get_boss(u);
parent[t2] = t1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //n个人
int m = sc.nextInt(); //m个关系
parent = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
Merge(a, b);
}
int count = 0;
for (int i = 1; i <= n; i++) {
if (parent[i] == i) {
count++;
}
}
System.out.println("团队数量:" + count);
}
}
朋友圈:https://leetcode-cn.com/problems/friend-circles/
public class P547FriendCircles {
/**
* [[1,1,0],
* [1,1,0],
* [0,0,1]]
* 输出: 2
*/
public static void main(String[] args) {
Solution solution = new P547FriendCircles().new Solution();
// TO TEST
System.out.println(solution.findCircleNum(new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
int[] parent = new int[200];
public int findCircleNum(int[][] M) {
int rows = M.length;
for (int i = 0; i < 200; i++) {
parent[i] = i;
}
for (int i = 0; i < rows; i++) {
for (int j = i + 1; j < rows; j++) {
if (M[i][j] == 1) {
merge(i, j);
}
}
}
int count = 0;
for (int i = 0; i < rows; i++) {
if (parent[i] == i) {
count++;
}
}
return count;
}
private int getParent(int x) {
return parent[x] == x ? x : getParent(parent[x]);
}
private void merge(int x, int y) {
int px = getParent(x);
int py = getParent(y);
parent[py] = px;
}
}
}