Juspay OA-1 2023

Problem Description

A React expert A is constantly being troubled by a React newbie B. The expert wants to block certain followers from his network in such a way that B can no longer reach out to him.

In this problem, the social network is modeled as a directed graph where:

• N is the total number of members in the network.
• Each member has an ID: MemberID_1, MemberID_2, MemberID_N.
• There are E edges (follower-following relationships) that describe how one person can follow another.
• A wants to find the minimum number of followers to block to prevent B from reaching him.

You need to determine the minimum set of followers of A that need to be removed from the network so that B cannot reach A anymore.

Input Format:

1. The first line contains an integer N, which represents the total number of members in the network.
2. The next N lines contain an integer, representing the Member ID of each member.
3. The next line contains an integer E, representing the total number of edges (follower-following relationships) in the network.
4. The next E lines contain two integers p_i and q_i, where:
   • p_i: The ID of the member who is following someone (the source of the connection).
   • q_i: The ID of the member being followed (the destination of the connection).
5. The last line contains two integers:
   • B (React newbie’s ID).
   • A (React expert’s ID).

Output Format:

• Set of followers that A needs to Block.

Sample Input:

4
2
5
7
9
4
2 9 
7 2
7 9
9 5
7
9

Sample Output:

2 7