SCC5 - Editorial

general
, , , ,
1

PROBLEM LINK:

Contest

Author: Chhekur

Tester: Pankaj Devesh

Editorialist: Pawan Kushwah

DIFFICULTY:

Easy

PREREQUISITES:

Stack, DP, Graph

PROBLEM:

You’re given a graph, you have to find out whether celebrity is alive or not.

EXPLANATION:

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.

2

this question can be done by making knows graph using adjacency list which will contain the no of people know to that particular node and also maintaining a know_by for each node which will contain the number of people that knows that node so now we have to find the node which does not knows anyone and which is know_by every one
here is a python implementation:-https://www.codechef.com/viewsolution/17237789
the complexity of the solution is O(n)