Round Table of Best Friends

Hard

A dinner is being held at a round table that can seat any number of people. There are n possible guests, numbered 0 to n - 1. Everyone has a best friend: buddy[i] is the best friend of guest i (always someone else). A guest will come only if they get to sit **next to** their best friend. Return the largest number of guests that can be invited and seated so that every invited guest sits next to their best friend.

Example 1

buddy=[1, 0, 1, 2] → 4

0 and 1 sit together, 2 sits next to 1, and 3 next to 2: going round the table 3, 2, 1, 0, everyone is happy.

Example 2

buddy=[1, 2, 3, 0, 0] → 4

0, 1, 2, 3 form a ring where everyone sits next to their friend. Guest 4 wants 0, but both of 0's neighbours are taken, so the answer is 4.

Example 3

buddy=[2, 0, 1, 4, 3] → 3

Constraints

n = len(buddy)
2 ≤ n ≤ 10⁵
0 ≤ buddy[i] ≤ n - 1
buddy[i] ≠ i

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Graph Topological Sort

Similar problems

Letter Order From a Dictionary Hard Longest Uphill Walk Hard Task Plan by Teams Hard Tree Path Without Twin Neighbours Hard Uphill-Only Walks Hard

Input

buddy=[1, 0, 1, 2]

Expected

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