Minimum Degree of a Connected Trio in a Graph — LeetCode 1761 Python Solution

The problem

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.

Example

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.

Python solution

def min(a: int, b: int) -> int:
    return a if a < b else b


class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        g = [[False] * n for _ in range(n)]
        deg = [0] * n
        for u, v in edges:
            u, v = u - 1, v - 1
            g[u][v] = g[v][u] = True
            deg[u] += 1
            deg[v] += 1
        ans = inf
        for i in range(n):
            for j in range(i + 1, n):
                if g[i][j]:
                    for k in range(j + 1, n):
                        if g[i][k] and g[j][k]:
                            ans = min(ans, deg[i] + deg[j] + deg[k] - 6)
        return -1 if ans == inf else ans

Complexity

Pattern: Depth-First Search

Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 1761. Minimum Degree of a Connected Trio in a Graph is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Graph.

The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.

Related problems