#P1139. Cat and Mouse
Cat and Mouse
题目描述
在一所拥有许多房间的房子里住着一只猫和一只老鼠。猫和老鼠各自选择了一个房间作为它们的“家”。它们会定期从自己的“家”出发在房子里走动。一只猫能够从房间A走到房间B,当且仅当从房间A到房间B有一扇猫门,并且猫门只能单向使用。类似地,一只老鼠能够从房间A走到房间B,当且仅当从房间A到房间B有一扇老鼠门,老鼠门同样只能单向使用。此外,猫不能使用老鼠门,老鼠也不能使用猫门。
给定房子的布局图,你需要编写一个程序来判断:
- 是否存在猫和老鼠的行走路线,使得它们在某个房间相遇;
- 老鼠是否能够经过至少两个房间,最后又回到它的“家”房间,并且在这个过程中永远不会遇到猫(这里,无论猫怎么走,老鼠都不能遇到猫)。

例如,在布局图中,猫可以在房间1、2和3中遇到老鼠。同时,老鼠可以经过两个房间而不遇到猫,比如从房间5到房间4再返回的一个往返路线。
输入格式
输入以一个单独的正整数开始,该正整数在一行中表示接下来的测试用例的数量,每个测试用例的描述如下。这一行后面跟着一个空行,并且在两个连续的输入之间也有一个空行。
输入由整数组成,定义了房子的布局。第一行有三个用空格分隔的整数:第一个整数表示房间的数量,第二个整数表示猫的初始房间(猫的“家”),第三个整数表示老鼠的初始房间(老鼠的“家”)。接下来有零行或多行,每行有两个用空格分隔的正整数。这些行之后跟着一行,该行有两个用空格分隔的-1。这些正整数对定义了猫门。数字对A B表示从房间A到房间B存在一扇猫门。最后有零行或多行,每行有两个用空格分隔的正整数。这些整数对定义了老鼠门。在这里,数字对A B表示从房间A到房间B存在一扇老鼠门。同样以-1,-1结束。
房间的数量至少为1且最多为100。所有房间从1开始连续编号。你可以假设输入中的所有正整数都是合法的房间编号。
输出格式
对于每个测试用例,输出必须遵循以下描述。
输出由两个用空格分隔的字符组成,并以换行符结尾。如果存在猫和老鼠的行走路线,使得它们在某个房间相遇,那么第一个字符是Y,否则是N。如果老鼠能够经过至少两个房间,最后又回到它的“家”房间,并且在这个过程中永远不会遇到猫,那么第二个字符是Y,否则是N。
1
5 2 4
1 2
2 1
3 1
4 3
5 2
-1 -1
1 3
2 5
3 4
4 1
4 2
4 5
5 4
-1 -1
Y Y
来源
1994年北美中东部地区