We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Degree of a Connected Trio in a Graph

Difficulty: Hard

Problem Description

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] = [u_i, v_i] indicates that there is an undirected edge between u_i and v_i. 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.

Key Insights

  • A connected trio consists of three nodes all connected to each other.
  • The degree of a trio can be calculated by counting the edges connecting the trio to other nodes.
  • We need to efficiently identify and evaluate all connected trios in the graph.
  • The problem can be approached using adjacency lists to represent the graph and a combination of nested loops to check for connected trios.

Space and Time Complexity

Time Complexity: O(n^3) in the worst case where we check all combinations of three nodes. Space Complexity: O(n + m) where n is the number of nodes and m is the number of edges for the adjacency list representation.

Solution

To solve the problem, we will represent the graph using an adjacency list. For each pair of nodes, we will check if a third node exists that is connected to both. If such a third node is found, we will then evaluate the degree of the connected trio by counting the edges connected to the trio that lead to other nodes. We will keep track of the minimum degree found among all trios. If no trios are found, we will return -1.

Code Solutions

def minimum_degree_of_connected_trio(n, edges):
    from collections import defaultdict
    
    # Create an adjacency list
    graph = defaultdict(set)
    for u, v in edges:
        graph[u].add(v)
        graph[v].add(u)

    min_degree = float('inf')
    found_trio = False

    # Check each pair of nodes
    for u in range(1, n + 1):
        for v in graph[u]:
            if u < v:  # To avoid counting the same pair twice
                # Find common neighbors
                common_neighbors = graph[u].intersection(graph[v])
                for w in common_neighbors:
                    found_trio = True
                    # Calculate degree of the trio (u, v, w)
                    degree = (len(graph[u]) - 2) + (len(graph[v]) - 2) + (len(graph[w]) - 2)
                    min_degree = min(min_degree, degree)

    return min_degree if found_trio else -1
← Back to All Questions