Minimum Degree of a Connected Trio in a Graph

Intuition

This problem doesn't need an algorithm, even dfs. We simply construct a adjancent metric. Then for each point, try to find if its 2 child are linked. If so, we can calculate the degree of the trio.

The worst time complexity is O(n ** 3).

Solution


class Solution:
    def minTrioDegree(self, n, edges):
        adjMetric = [[False] * n for _ in range(n)]
        for point1, point2 in edges:
            point1, point2 = point1 - 1, point2 - 1
            adjMetric[point1][point2] = True
            adjMetric[point2][point1] = True
        degree = [sum(row) for row in adjMetric]

        minDegree = float('inf')
        for point1 in range(n):
            for point2 in range(point1 + 1, n):
                for point3 in range(point2 + 1, n):
                    if adjMetric[point1][point2] \
                            and adjMetric[point2][point3] \
                            and adjMetric[point3][point1]:
                        minDegree = min(
                            minDegree,
                            degree[point1] + degree[point2] + degree[point3] - 6
                        )
        if minDegree == float('inf'):
            return -1
        return minDegree