Breaking the Friend Chain

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type

Thanks to the growing influence of Facebook on our lives, people can be connected even if they think they're not. Even if someone is not your friend, it doesn't mean none of your friends has them as a friend, and their friends, and their friends' friends… The International Society of Unfriendliness and War has some connections between people to break. To do this, they will have to disable some Facebook accounts, as this will effectively ruin all the owner's connections, and disconnect their friendships.

To see how much effort it is to disconnect a given pair of people, they have hired you to find the minimum number of Facebook accounts they need to disable.

Input Specification

The first line is a pair of two numbers, N and M, where N, M \in \mathbb N; 2 \le N \le 10\,000 and M \le 20\,000, the number of people and the number of friendships, respectively. The next M lines are pairs of two integers, A and B, the id of the two people who are friends, where A, B \in \mathbb N; A, B \le N. You may assume no one can be friends with oneself. The next line will be two integers, X and Y, the two people to disconnect, following the same format as A and B.

The International Society of Unfriendliness and War has some bad news for you. The friends data were acquired illegally, so its quality is not guaranteed. In particular, if A is listed as B's friend, there is a chance B will also be listed as A's friend, even though it is implied that this is the case.

Output Specification

Output the minimum number of Facebook accounts that need to be disabled to disconnect X and Y.

Sample Input 1

3 2
1 2
2 3
1 3

Sample Output 1


Explanation of Sample 1

There are three people and two friend relations: 1 is friends with 2, who is friends with 3. If we disable 2's Facebook account, 1 can no longer reach 3. There is no better way to ruin the link between 1 and 3. Therefore, we output 1 as we need to destroy a minimum of one Facebook account.

Sample Input 2

4 2
2 3
3 1
1 4

Sample Output 2


Explanation of Sample 2

There are no links between 1 and 4 in the first place, so no shady business needs to be done.


  • 0
    b_nary  commented on Nov. 8, 2023, 5:03 a.m.

    idk why i didnt realize you can just disable X

  • 3
    OneYearOld  commented on Jan. 10, 2021, 10:52 p.m. edited

    This problem is the graph theory variant of List Minimum (Easy) in the sense that it seems impossible until you think about it for long enough, and then it becomes much easier.

  • 15
    Epicnerdking  commented on Feb. 6, 2017, 2:13 a.m.

    "You may assume no one can be friends with oneself." Ouch.

    • 0
      VictorZhu  commented on Oct. 15, 2022, 5:16 p.m.

      Imagine not having friends ... 😭