#1761
Minimum Degree of a Connected Trio in a Graph
master · 1635 · lc hard +32 · verified · 44.3% accepted · 358 likes · top 27%
Description
You are given an undirected graph with n nodes and edges[i] = [ui, vi]. A connected trio is three nodes where every pair is connected. The degree of a trio is the number of edges with exactly one endpoint inside the trio. Return the minimum degree of any connected trio, or -1 if none exists.
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.
Code
1
2
3