Minimum Degree Of A Connected Trio In A Graph - Leetcode Solution

Problem Statement:

Given an undirected graph, return the minimum degree of a connected trio in the graph. A connected trio is a set of three nodes where there is an edge between every pair of them.

Example 1:

Input: graph = [[1,2,3],[0,4,5],[0,4,6],[0,5,6],[1,2,7],[1,3,7],[2,3,8],[4,6,8],[5,7,8]] Output: 3 Explanation: The smallest degree is the degree of vertex 7 which is 3.

Solution:

We can solve this problem by iterating over all possible triples of vertices in the graph and checking whether they form a connected trio. In order to efficiently check whether a triple is connected, we can use breadth-first search or depth-first search to explore the subgraph induced by the triple.

To optimize the solution, we can first compute the degree of each vertex in the graph. We can then iterate over all pairs of vertices in the graph, and for each pair (u, v), we can iterate over all neighbors w of both u and v. If u, v, and w form a connected trio, then we update the minimum degree accordingly.

The time complexity of this solution is O(n^3), where n is the number of vertices in the graph. However, in practice, the solution should be able to solve most inputs of the size given in the problem statement.

Here's the Python code with comments that implements this solution:

class Solution: def minTrioDegree(self, n: int, edges: List[List[int]]) -> int: # Initialize the graph as an adjacency list graph = [[] for _ in range(n+1)] for u, v in edges: graph[u].append(v) graph[v].append(u)

    # Compute the degree of each vertex in the graph
    degree = [len(graph[u]) for u in range(n+1)]

    # Iterate over all pairs of vertices in the graph
    min_degree = float('inf')
    for u in range(1, n+1):
        for v in range(u+1, n+1):
            if v in graph[u]:
                # Iterate over all neighbors of both u and v
                for w in graph[u]:
                    if w in graph[v]:
                        # Check whether u, v, and w form a connected trio
                        degree_uvw = degree[u] + degree[v] + degree[w] - 6
                        min_degree = min(min_degree, degree_uvw)

    # Return the minimum degree of a connected trio in the graph
    return -1 if min_degree == float('inf') else min_degree

Time Complexity: O(n^3), where n is the number of vertices in the graph.

1