#
# @lc app=leetcode id=277 lang=python3
#
# [277] Find the Celebrity
#
# https://leetcode.com/problems/find-the-celebrity/description/
#
# algorithms
# Medium (40.96%)
# Likes:    1027
# Dislikes: 128
# Total Accepted:    118.8K
# Total Submissions: 289.7K
# Testcase Example:  '[[1,1,0],[0,1,0],[1,1,1]]'
#
# Suppose you are at a party with n people (labeled from 0 to n - 1) and among
# them, there may exist one celebrity. The definition of a celebrity is that
# all the other n - 1 people know him/her but he/she does not know any of
# them.
# 
# Now you want to find out who the celebrity is or verify that there is not
# one. The only thing you are allowed to do is to ask questions like: "Hi, A.
# Do you know B?" to get information of whether A knows B. You need to find out
# the celebrity (or verify there is not one) by asking as few questions as
# possible (in the asymptotic sense).
# 
# You are given a helper function bool knows(a, b) which tells you whether A
# knows B. Implement a function int findCelebrity(n). There will be exactly one
# celebrity if he/she is in the party. Return the celebrity's label if there is
# a celebrity in the party. If there is no celebrity, return -1.
# 
# 
# 
# Example 1:
# 
# 
# Input: graph = [
# [1,1,0],
# [0,1,0],
# [1,1,1]
# ]
# Output: 1
# Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1
# means person i knows person j, otherwise graph[i][j] = 0 means person i does
# not know person j. The celebrity is the person labeled as 1 because both 0
# and 2 know him but 1 does not know anybody.
# 
# 
# Example 2:
# 
# 
# Input: graph = [
# [1,0,1],
# [1,1,0],
# [0,1,1]
# ]
# Output: -1
# Explanation: There is no celebrity.
# 
# 
# 
# 
# Note:
# 
# 
# The directed graph is represented as an adjacency matrix, which is an n x n
# matrix where a[i][j] = 1 means person i knows person j while a[i][j] = 0
# means the contrary.
# Remember that you won't have direct access to the adjacency matrix.
# 
# 
#

# @lc code=start
# 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:
        possible_celebrity = 0
        for i in range(1, n):
            if knows(possible_celebrity, i):
                possible_celebrity = i
        for i in range(n):
            if possible_celebrity != i and \
                (knows(possible_celebrity, i) or not knows(i, possible_celebrity)):
                return -1
        return possible_celebrity
# @lc code=end

#
# @lc app=leetcode id=277 lang=python3
#
# [277] Find the Celebrity
#
# https://leetcode.com/problems/find-the-celebrity/description/
#
# algorithms
# Medium (40.96%)
# Likes:    1027
# Dislikes: 128
# Total Accepted:    118.8K
# Total Submissions: 289.7K
# Testcase Example:  '[[1,1,0],[0,1,0],[1,1,1]]'
#
# Suppose you are at a party with n people (labeled from 0 to n - 1) and among
# them, there may exist one celebrity. The definition of a celebrity is that
# all the other n - 1 people know him/her but he/she does not know any of
# them.
# 
# Now you want to find out who the celebrity is or verify that there is not
# one. The only thing you are allowed to do is to ask questions like: "Hi, A.
# Do you know B?" to get information of whether A knows B. You need to find out
# the celebrity (or verify there is not one) by asking as few questions as
# possible (in the asymptotic sense).
# 
# You are given a helper function bool knows(a, b) which tells you whether A
# knows B. Implement a function int findCelebrity(n). There will be exactly one
# celebrity if he/she is in the party. Return the celebrity's label if there is
# a celebrity in the party. If there is no celebrity, return -1.
# 
# 
# 
# Example 1:
# 
# 
# Input: graph = [
# [1,1,0],
# [0,1,0],
# [1,1,1]
# ]
# Output: 1
# Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1
# means person i knows person j, otherwise graph[i][j] = 0 means person i does
# not know person j. The celebrity is the person labeled as 1 because both 0
# and 2 know him but 1 does not know anybody.
# 
# 
# Example 2:
# 
# 
# Input: graph = [
# [1,0,1],
# [1,1,0],
# [0,1,1]
# ]
# Output: -1
# Explanation: There is no celebrity.
# 
# 
# 
# 
# Note:
# 
# 
# The directed graph is represented as an adjacency matrix, which is an n x n
# matrix where a[i][j] = 1 means person i knows person j while a[i][j] = 0
# means the contrary.
# Remember that you won't have direct access to the adjacency matrix.
# 
# 
#

# @lc code=start
# 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:
        possible_celebrity = 0
        for i in range(1, n):
            if knows(possible_celebrity, i):
                possible_celebrity = i
        for i in range(n):
            if possible_celebrity != i and \
                (knows(possible_celebrity, i) or not knows(i, possible_celebrity)):
                return -1
        return possible_celebrity
# @lc code=end

# # @lc app=leetcode id=277 lang=python3 # # [277] Find the Celebrity # # https://leetcode.com/problems/find-the-celebrity/description/ # # algorithms # Medium (40.96%) # Likes:    1027 # Dislikes: 128 # Total Accepted:    118.8K # Total Submissions: 289.7K # Testcase Example:  '[[1,1,0],[0,1,0],[1,1,1]]' # # Suppose you are at a party with n people (labeled from 0 to n - 1) and among # them, there may exist one celebrity. The definition of a celebrity is that # all the other n - 1 people know him/her but he/she does not know any of # them. # # Now you want to find out who the celebrity is or verify that there is not # one. The only thing you are allowed to do is to ask questions like: "Hi, A. # Do you know B?" to get information of whether A knows B. You need to find out # the celebrity (or verify there is not one) by asking as few questions as # possible (in the asymptotic sense). # # You are given a helper function bool knows(a, b) which tells you whether A # knows B. Implement a function int findCelebrity(n). There will be exactly one # celebrity if he/she is in the party. Return the celebrity's label if there is # a celebrity in the party. If there is no celebrity, return -1. # # # # Example 1: # # # Input: graph = [ # [1,1,0], # [0,1,0], # [1,1,1] # ] # Output: 1 # Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 # means person i knows person j, otherwise graph[i][j] = 0 means person i does # not know person j. The celebrity is the person labeled as 1 because both 0 # and 2 know him but 1 does not know anybody. # # # Example 2: # # # Input: graph = [ # [1,0,1], # [1,1,0], # [0,1,1] # ] # Output: -1 # Explanation: There is no celebrity. # # # # # Note: # # # The directed graph is represented as an adjacency matrix, which is an n x n # matrix where a[i][j] = 1 means person i knows person j while a[i][j] = 0 # means the contrary. # Remember that you won't have direct access to the adjacency matrix. # # # # @lc code=start # The knows API is already defined for you. # return a bool, whether a knows b # def knows(a: int, b: int) -> bool: # @lc code=end