The Loosest Triangle

Hard

You are given an undirected graph with n vertices numbered 1 to n and a list links, where links[i] = [u, v] connects u and v. No pair is linked twice. A triangle is a set of three vertices that are all linked to each other. For a triangle, count the links that lead from its vertices to vertices outside it. Return the smallest such count over all triangles in the graph, or -1 if there are none.

Example 1

n=5, links=[[1, 2], [2, 3], [3, 1], [3, 4], [4, 5], [5, 3]] → 2

There are two triangles, {1, 2, 3} and {3, 4, 5}. Each has two links leaving it, both from vertex 3, so the answer is 2.

Example 2

n=4, links=[[1, 2], [2, 3], [3, 4], [4, 1]] → -1

This is a 4-cycle with no triangles.

Example 3

n=6, links=[[1, 2], [1, 3], [2, 3], [4, 5], [4, 6], [5, 6], [3, 4]] → 1

Constraints

2 ≤ n ≤ 400
1 ≤ len(links) ≤ n · (n - 1) / 2
1 ≤ u, v ≤ n, u ≠ v
Every pair of vertices is linked at most once

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph

Similar problems

Letter Order From a Dictionary Hard Longest Uphill Walk Hard Route Through Every Boarding Pass Hard Ball Into the Hole Hard The Extra Link in a Rooted Tree Hard

Input

n=5, links=[[1, 2], [2, 3], [3, 1], [3, 4], [4, 5], [5, 3]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 60 tests on the server, hidden ones included.