LeetCode 1761 Minimum Degree of a Connected Trio in a Graph

LeetCode

You are given an undirected graph. You are given an integer n which is the number of nodes in the graph and an array edges, where each edges[i] = [ui, vi] indicates that there is an undirected edge between ui and vi.

A connected trio is a set of three nodes where there is an edge between every pair of them.

The degree of a connected trio is the number of edges where one endpoint is in the trio, and the other is not.

Return the minimum degree of a connected trio in the graph, or -1 if the graph has no connected trios.

Example 1:

Input: n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
Output: 3
Explanation: There is exactly one trio, which is [1,2,3]. The edges that form its degree are bolded in the figure above.

Example 2:

Input: n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
Output: 0
Explanation: There are exactly three trios:
1) [1,4,3] with degree 0.
2) [2,5,6] with degree 2.
3) [5,6,7] with degree 2.

Constraints:

2 <= n <= 400 edges[i].length == 2
`1 <= edges.length <= n (n-1) / 2*1 <= u_i, v_i <= n*u_i != v_i`
* There are no repeated edges.

题目大意：

给定一个图，trio是三个节点直接互相相连，而度数表示连着trio的边的个数

解题思路：

根据定义，找出所有三个节点的组合，判断是否trio，然后根据trio的每个节点的度数总和 - 6即为所求
遍历所有三个节点组合时，会重复了两次。所以一个优化是，先按度数排序节点，若节点度数大于等于最小度数除以3，跳出循环。因为这个最小度数的节点已经大于等于3，trio里其他两个度数比它大的节点的度数更加会大于最小度数除以3，这样总度数肯定大于此时的最小度数

解题步骤：

N/A

注意事项：

根据定义，找出所有三个节点的组合u -> v, v -> w, w是否在u中，判断是否trio。先按度数排序节点，若节点度数大于等于最小度数除以3，跳出循环
邻接图用set，因为Line 13查找w是否在u中可以提高效率
min_degree / 3不是// 3

Python代码：

def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
	graph = collections.defaultdict(set) # use set coz if w in graph[u]
	for u, v in edges:
		graph[u].add(v)
		graph[v].add(u)

	min_degree = float('inf')
	for u in sorted(range(1, n + 1), key=lambda x: len(graph[x])):
		if len(graph[u]) >= min_degree / 3: # remember / 3 not // 3
			break
		for v in graph[u]:
			for w in graph[v]:
				if w in graph[u]:
					min_degree = min(min_degree, len(graph[u]) + len(graph[v]) + len(graph[w]))
	return min_degree - 6 if min_degree != float('inf') else -1

算法分析：

时间复杂度为O(n³)，空间复杂度O(n²)