Last Updated: 27 Mar, 2021
Find the Town Judge
Moderate
Asked in companies
In a town, there are ‘N’ people, each person number from [1, 'N']. We know that one of these people is a secret judge. There are the following facts related to the judge:
1. The judge trust nobody
2. Everybody trusts the judge
3. There is only one judge.
You are given an array/list of pairs, representing that the first value of the pair trusts the second value of the pair. You need to find the town judge. If there is no possible judge return -1.
Note:
Note that the judge is also numbered similar to the rest of the town members.
Input Format:
The first line contains an integer ‘T’ which denotes the number of test cases.
The first line of each test case contains two space-separated integers ‘N’ and ‘X’, denoting the number of people in the town and the number of queries regarding who trusts whom.
The next ‘X’ lines of each test contain an array of ‘X’ pairs where each pair denotes who trusts whom in the town.
Output Format:
For each test case, you need to return a single integer denoting the judge.
Print the output of each test case in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 1000
0 <= X <= 1000
1 <= Y1, Y2 <= N
Where 'Y1' and 'Y2' denotes who trusts whom in the town.
Time limit: 1 sec
Approaches
In this approach, we will be creating two arrays to count the number of incoming and outgoing edges on a certain person. For any outgoing edges let’s say from A to B, we will surely know that A is not the judge, as A trusts B but a judge doesn't trust anyone.
For incoming edges A to B, we increment the counter of count[B], where the count is the array used. When we know there are ‘N’ - 1 incoming connection, we store B, as it is a possible candidate for being the judge, and move forward. If we come through another candidate let’s say C that also has ‘N’ - 1 incoming connection, we know that no possible judge or answer is valid. So return -1.
The steps are as follows:
- Create two vectors and initialize their values to 0. These will store the count of each incoming connection and outgoing connections.
- Start traversing through each node and increase incoming connections for every second value of the given pair and increase outgoing connections for every first value of the pair.
- Now, check for a node that has incoming connection = ‘N’ - 1 and outgoing connections = 0 at the same time
- Node found:
- Return node
- Not found:
- Return -1
- Node found:
Similar problems