九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1401-九度Online Judge,用代码记录你的成长之路!

题目1401:阿里巴巴和N个强盗

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:258

解决:27

题目描述:
         大家都读过《水浒传》吧?即使没有读过,也应该看过电视剧吧?如果上面两个问题你的回答都是否,那就赶快面壁思过吧。
         好吧,我们今天要说的不是水浒传。
         在很久很久以前,有一个人叫做阿里巴巴,自此开始了阿里巴巴和N个强盗的故事(此处省略一万字)。
        
         好吧,我又卖关子了,今天的重点是N个强盗之间的故事。
         水浒传中的108个好汉(及好女子)会有一个排名,N个强盗之间也要排出一个名次来。不可否认,有许多盗窃团伙很专业,其中也不乏严格的规矩。但这N个强盗是个无组织、无纪律的团伙,他们之间的排序完全是根据一场决斗来定的,比如在一场决斗中,强盗A战胜了强盗B,那么就说强盗A的排名高于强盗B。决斗是随机发生的,也就是哪天两个强盗互相看不惯对方了,那么就开始一场决斗。而这样产生的结果就是,有可能拿出两个强盗来,我们根本就不知道这两个强盗到底谁更厉害一些。这没有关系,今天你只要给出能根据我给你的信息来判断出某两个强盗谁的排名更靠前一些就行。
         你需要注意的是,强盗之间的排名有传递性,比如强盗A的排名比强盗B靠前,而强盗B的排名又比强盗C的靠前,那么我们就认为强盗A的排名要比强盗C的靠前。
         现在,我能给你的信息是强盗之间发生决斗的次数,以及每次参加决斗的两名强盗的姓名及最后决斗的结果。
输入:
         输入可能包括多组测试数据,对于每组测试数据,
输入的第一行是一个整数N(2<=N<=100000),代表强盗的个数,以及一个整数M(1 <= M <= 5*10^9),表示强盗之间发生决斗的次数。
         接下来的M行每行包括两个强盗的姓名(每个强盗的姓名为一个字符串,且字符串的长度不超过100),以及最后决斗的结果。最后的结果为”WIN”表示前一个强盗取得了胜利,最后的结果为”LOSE”表示后一个强盗取得了胜利。
         每组测试数据的最后一行包括我们要询问的两个强盗的姓名(每个强盗的姓名为一个字符串,且字符串的长度不超过100)。
输出:
对于每组测试数据,对于我们要询问的两个强盗,
如果前一个强盗的排名比后一个强盗的靠前,则输出”WIN”(注意,输出时不加双引号);
如果后一个强盗的排名比前一个强盗的靠前,则输出”LOSE”(注意,输出时不加双引号);
如果你通过我们给出的数据无法判断两个强盗的排名的先后关系,那么请输出”MY GOD”(注意,输出时不加双引号)。
样例输入:
5 3
A B WIN
B C WIN
D E WIN
D C
5 3
A B WIN
B C WIN
E F LOSE
A C
4 3
A B WIN
C D LOSE
D A WIN
A C
3 3
A B WIN
B C WIN
C A WIN
A B
样例输出:
LOSE
WIN
WIN
MY GOD
提示:
         1.如果强盗A战胜了强盗B,强盗B战胜了强盗C,那么我们说强盗A的排名要比强盗C的排名靠前。
         2.如果强盗A战胜了强盗B,同时,强盗A战胜了强盗D,那么我们认为强盗B的排名要比强盗D靠前。也就是说,两个强盗都能被第三个强盗战胜(包括传递性的战胜,如提示1所说),那么名字的字典序靠前的强盗排名较为靠前。同时,如果两个强盗在两个比较关系链中,例如Sample Input中第一组样例,两个比较关系链分别为:A->B->C, D->E,那么根据字典序靠前的强盗排名靠前原则,A的排名要比D靠前,接着往下看,B的排名也要比D靠前,同时,C的排名也要比D靠前。现在,我们如果换一下,两个比较关系链如果为A->F->C, D->E,那么结果就是:A的排名比D的靠前,但是D的排名比F的靠前,很显然,由于F的排名本身就比C靠前,所以D的排名也就比C靠前。
         3.我们保证在每场决斗中两个强盗一定能分出胜负。
         4.注意,虽然我们给出有N个强盗,但这N个强盗在下面给出的M场决斗中不一定会出现。
答疑:
解题遇到问题?分享解题心得?讨论本题请访问:http://t.jobdu.com/thread-8128-1-1.html