Tester: Pankaj Devesh
Editorialist: Pawan Kushwah
Stack, DP, Graph
You’re given a graph, you have to find out whether celebrity is alive or not.
In order to solve this problem, first you have to make a matrix of given graph then you have to find a row, which is only filled with 0’s. And a column equivalent to this row, which is filled with 1’s except at this row index. The index of this column is celebrity.
If there is no shuch row and column exist in given graph then there is no celebrity.
Complexity of this solution is O(n).
Author’s solution can be found here.