https://leetcode.com/problems/count-the-number-of-complete-components
2685. Count the Number of Complete Components
給你一個陣列表示無向圖的邊，找出共有幾個完整元件，完整元件被定義成所有點都有
邊連起來的圖，只有一個點也是完整元件。
思路:
1.先用題目給的邊建圖，順便用併查集對每個點分組。
2.檢查每個組別的所有點，他的邊的數量-1 是否等於該組別的點的數量，是的話表示這
組是一個完整元件。
Java Code:
------------------------------------------------------
class Solution {
public int countCompleteComponents(int n, int[][] edges) {
int[] root = new int[n];
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
root[i] = i;
graph.put(i, new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
int y = find(root, edge[0]);
int x = find(root, edge[1]);
root[y] = x;
}
// 更新父節點
for (int i = 0; i < n; i++) {
find(root, i);
}
int res = 0;
for (int i = 0; i < n; i++) {
// 忽略算過的
if (root[i] == -1) {
continue;
}
int countOfVertex = 0;
for (int j = 0; j < n; j++) {
if (root[j] == root[i]) {
countOfVertex++;
}
}
boolean ok = true;
int rootId = root[i];
for (int j = 0; j < n; j++) {
if (root[j] == rootId) {
root[j] = -1;
if (graph.get(j).size() + 1 != countOfVertex) {
ok = false;
}
}
}
if (ok) {
res++;
}
}
return res;
}
int find(int[] root, int x) {
return root[x] == x ? x : (root[x] = find(root, root[x]));
}
}
------------------------------------------------------
--
你跟我說這個我有什麼辦法
https://i.imgur.com/wb5zrOy.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1742630623.A.378.html