PROBLEM LINK:
Author: admin5
Tester: admin6
Editorialist: admin5
DIFFICULTY:
EASY
PREREQUISITES:
Graph, Hashing
PROBLEM:
Your are given N number of persons and M relation between them. Next M line contains relation between two persons, and you are asked to find out who will die first.
QUICK EXPLANATION:
Your are given N number of persons and M relation between them. There are two kinda people Innocent and Dangerous people, In M lines you are given relation between two persons along with their status whether they are Innocent or Dangerous or one is Innocent and another one is Dangerous or vice versa.
In this question you just need to find out a Innocent person who has maximum connection with Dangerous persons, In case of tie with two or more persons you just need to print them all in increasing order.
DETAILED EXPLANATION:
In order to solve this problem you can build a Hash Map of only Innocent persons from N persons because according to problem statement Government is interested to save only Innocent people.
Then for each relation, we can check if First person is Innocent and Second person is Dangerous then we can increment the connection of First person by one (because relation is directed).
After all M relations you just need to print the key of Hash Map which having maximum relation or in case of tie, print all of them in increasing order.
Time complexity of this approach is O(M+M) = O(2M) = O(M)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.