题目 #

You are given an integer n. There is an undirected graph with n vertices, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting vertices ai and bi.

Return the number of complete connected components of the graph.

A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.

A connected component is said to be complete if there exists an edge between every pair of its vertices.

Example 1:

Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
Output: 3
Explanation: From the picture above, one can see that all of the components of this graph are complete.

Example 2:

Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
Output: 1
Explanation: The component containing vertices 0, 1, and 2 is complete since there is an edge between every pair of two vertices. On the other hand, the component containing vertices 3, 4, and 5 is not complete since there is no edge between vertices 4 and 5. Thus, the number of complete components in this graph is 1.

Constraints:

1 <= n <= 50
0 <= edges.length <= n * (n - 1) / 2
edges[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
There are no repeated edges.

思路1 并查集找关系，计算边数量 #

分析 #

并查集可以将在一起的点合并成一个集合
对每个集合计算边的数量，每个集合v个节点，边的数量为 $\frac{v(v-1)}{2}$

代码 #

 1func countCompleteComponents(n int, edges [][]int) int {
 2	// 使用并查集合并所有的点
 3	// 并查集模板
 4	uf := make([]int, n)
 5	for i := range uf {
 6		uf[i] = i
 7	}
 8	find := func(x int) int {
 9		ap := uf[x]
10		// 找到最终节点
11		for ap != uf[ap] {
12			ap = uf[ap]
13		}
14		// 沿途都赋值最终节点
15		for x != ap {
16			uf[x], x = ap, uf[x]
17		}
18		return ap
19	}
20	// 把a的子集合并到b上，如果b是树根节点，a的所有子节点查找都会查找到b
21	merge := func(a, b int) {
22		uf[find(a)] = find(b)
23	}
24
25	// 并查集整理好
26	for _, v := range edges {
27		merge(v[0], v[1])
28	}
29
30	// 并查集的每个集合统计点数和边数
31	pCnt := make([]int, n)
32	eCnt := make([]int, n)
33	for i := 0; i < n; i++ {
34		pCnt[find(i)]++
35	}
36	for _, v := range edges {
37		eCnt[find(v[0])]++
38	}
39
40	// 判断数量
41	res := 0
42	for i, v := range pCnt {
43		if v == 0 {
44			continue
45		}
46		if v*(v-1)/2 == eCnt[i] {
47			res++
48		}
49	}
50	return res
51}

思路2 #

分析 #

使用dfs从每个点开始走，能走到的点都是联通块的点
统计这个联通块所有点的边数，联通块的点数，按照 $eCnt = pCnt \times (pCnt-1)$ 计算

代码 #

 1func countCompleteComponents(n int, edges [][]int) int {
 2	g := make([][]int, n)
 3	for _, e := range edges {
 4		x, y := e[0], e[1]
 5		g[y] = append(g[y], x)
 6		g[x] = append(g[x], y)
 7	}
 8
 9	vis := make([]bool, n)
10	pCnt := 0
11	eCnt := 0
12	var dfs func(x int)
13	dfs = func(x int) {
14		vis[x] = true
15		pCnt++
16		eCnt += len(g[x])
17		for _, v := range g[x] {
18			if !vis[v] {
19				dfs(v)
20			}
21		}
22	}
23	res := 0
24	for i := 0; i < n; i++ {
25		if !vis[i] {
26			eCnt, pCnt = 0, 0
27			dfs(i)
28			if pCnt*(pCnt-1) == eCnt {
29				res++
30			}
31		}
32	}
33	return res
34}