Leetcode Problem 1761. Minimum Degree of a Connected Trio in a Graph

1761. Minimum Degree of a Connected Trio in a Graph

Leetcode Solutions

Using Adjacency Matrix and Degree Count

  1. Initialize an adjacency matrix am with dimensions (n+1) x (n+1) and set all values to 0.
  2. Initialize a degree count array cnt with length n+1 and set all values to 0.
  3. Iterate over each edge in edges and update the adjacency matrix and degree count array accordingly.
  4. Initialize a variable res to positive infinity to store the minimum degree of a connected trio.
  5. Iterate through all possible trios of nodes (t1, t2, t3).
  6. If am[t1][t2], am[t1][t3], and am[t2][t3] are all 1, then nodes t1, t2, and t3 form a connected trio.
  7. Calculate the degree of the trio as cnt[t1] + cnt[t2] + cnt[t3] - 6 and update res if it's smaller.
  8. After checking all trios, return -1 if res is still positive infinity, indicating no trios were found. Otherwise, return res.
UML Thumbnail

Using Adjacency List and Set Intersection

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...