[Leetcode/Graph (In-Degree/Out-Degree)] 277. Find the Celebrity

# The knows API is already defined for you.
# return a bool, whether a knows b
# def knows(a: int, b: int) -> bool:

class Solution:
    def findCelebrity(self, n: int) -> int:
        # Step 1: Find the celebrity candidate
        candidate = 0
        for i in range(1, n):
            if knows(candidate, i):
                # Candidate knows i → candidate is not the celebrity
                candidate = i
            # Else: candidate doesn't know i → i can't be the celebrity
        
        # Step 2: Verify the candidate
        for i in range(n):
            if i == candidate:
                continue
            # Candidate must not know anyone else
            # Everyone else must know the candidate
            if knows(candidate, i) or not knows(i, candidate):
                return -1
        
        return candidate