Three-Room Loops

Medium

An escape game has rooms rooms numbered from 1 to rooms. Some pairs of rooms are linked by doors: doors[i] = [a, b] means you can walk between rooms a and b in either direction. A three-room loop is a set of three distinct rooms where each room has a door to both of the others. Two loops are the same if they consist of the same rooms, no matter the order you walk them in. Return the number of distinct three-room loops.

Example 1

rooms=5, doors=[[1, 2], [2, 3], [3, 1], [3, 4], [4, 5]] → 1

The only loop is made of rooms 1, 2 and 3.

Example 2

rooms=4, doors=[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] → 4

Every pair of the four rooms is connected, so any three rooms form a loop: {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}.

Example 3

rooms=3, doors=[[1, 2], [2, 3]] → 0

There is no door from room 3 back to room 1, so there is no loop.

Constraints

2 ≤ rooms ≤ 10⁴
1 ≤ len(doors) ≤ 5·10⁴
doors[i] = [a, b], 1 ≤ a, b ≤ rooms, a ≠ b
Any two rooms share at most one door

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph

Similar problems

Module Build Order Medium Course Enrollment Queue Medium Do the Links Form a Tree Medium Best Roots for a Tree Medium Isolated Groups in a Network Medium

Input

rooms=5, doors=[[1, 2], [2, 3], [3, 1], [3, 4], [4, 5]]

Expected

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