Minimum Degree of a Connected Trio in a Graph

Minimum Degree of a Connected Trio in a Graph - Problem

Graph Enumeration Hard

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.

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.

Input & Output

Example 1 — Basic Connected Trio

$ Input: n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]

› Output: 3

💡 Note: There are exactly 3 trios: (1,2,3), (1,2,4), and (2,3,5). The trio (1,2,3) has degree 3 (node 1 connects to 4, node 2 connects to 5, node 3 connects to 6), which is minimum.

Example 2 — No Connected Trios

$ Input: n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7]]

› Output: -1

💡 Note: No set of 3 nodes forms a complete triangle where every pair is connected.

Example 3 — Perfect Triangle

$ Input: n = 3, edges = [[1,2],[2,3],[1,3]]

› Output: 0

💡 Note: The only trio is (1,2,3) and all three nodes only connect to each other, so external degree is 0.

Constraints

2 ≤ n ≤ 400
edges.length ≤ n * (n-1) / 2
edges[i].length == 2
1 ≤ ui, vi ≤ n
ui != vi
There are no repeated edges

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Graph with n=6 nodes and given edges

Find Trios

Identify all connected triangles

Calculate Degrees

Count external edges for each trio

Key Takeaway

🎯 Key Insight: A trio's degree = sum of node degrees - 6 (internal triangle edges)

Asked in

f Facebook 35 G Google 28 a Amazon 22

The key insight is that a connected trio's degree equals the sum of individual node degrees minus 6 (the internal trio edges). The optimized approach uses adjacency sets to efficiently find trios by checking common neighbors for each edge. Time: O(m × min(deg(u), deg(v))), Space: O(n + m).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Adjacency Set	O(m · min(deg(u), deg(v)))	O(n + m)	Use adjacency sets for O(1) edge lookup and optimize trio checking
Brute Force Triple Check	O(n³ + m)	O(n²)	Check all possible combinations of 3 nodes and verify if they form a connected trio

Optimized with Adjacency Set — Algorithm Steps

Build adjacency sets for O(1) edge checking
For each edge (u,v), find common neighbors
Each common neighbor w forms trio (u,v,w)
Calculate trio degree efficiently

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Adjacency Sets

Create fast lookup structure for edges

Process Each Edge

For edge (u,v), find common neighbors

Calculate Degrees

Sum individual degrees minus trio's internal edges

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_N 400

int solution(int n, int edges[][2], int edgeCount) {
    // Build adjacency matrix and degree count
    int adjMatrix[MAX_N][MAX_N] = {0};
    int degree[MAX_N] = {0};
    
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0] - 1, v = edges[i][1] - 1;
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1;
        degree[u]++;
        degree[v]++;
    }
    
    int minDegree = INT_MAX;
    
    // For each edge, find common neighbors
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0] - 1, v = edges[i][1] - 1;
        // Find intersection of neighbors
        for (int w = 0; w < n; w++) {
            if (adjMatrix[u][w] && adjMatrix[v][w] && w != u && w != v) {
                // Found trio (u, v, w)
                int trioDegree = degree[u] + degree[v] + degree[w] - 6;
                if (trioDegree < minDegree) {
                    minDegree = trioDegree;
                }
            }
        }
    }
    
    return minDegree == INT_MAX ? -1 : minDegree;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int edges[1000][2];
    int edgeCount = 0;
    char* ptr = line + 1;
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            edges[edgeCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            edges[edgeCount][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            edgeCount++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(n, edges, edgeCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m · min(deg(u), deg(v)))

For each edge, check intersection of neighbor sets

✓ Linear Growth

Space Complexity

O(n + m)

Adjacency sets store all edges and degrees

⚡ Linearithmic Space

33.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Adjacency Set — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler