STL set 应用 HDU2096 产生冠军

青旅半醒 2024-01-11 06:29 7阅读 0赞

## 产生冠军 ##

**Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 25048 Accepted Submission(s): 11194**

Problem Description

有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。  
球赛的规则如下：  
如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定，A一定能打败C。  
如果A打败了B，B又打败了C，而且，C又打败了A，那么A、B、C三者都不可能成为冠军。  
根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。

Input

输入含有一些选手群，每群选手都以一个整数n(n<1000)开头，后跟n对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示，前者战胜后者。如果n为0，则表示输入结束。

Output

对于每个选手群，若你判断出产生了冠军，则在一行中输出“Yes”，否则在一行中输出“No”。

Sample Input

3 Alice Bob Smith John Alice Smith 5 a c c d d e b e a d 0

Sample Output

Yes No

Author

qianneng

Source

[迎接新学期——超级Easy版热身赛 ][Easy_]

Recommend

lcy | We have carefully selected several similar problems for you: [2093][] [1811][] [2086][] [3342][] [2647][]

思路：

开两个集合，一个胜利者集合，一个失败者集合。

遍历一遍失败者集合，如果在失败者集合中找到胜利者的元素，在胜利者集合中把该元素删了。

如果胜利者集合最后大小为1，则能；否则，不能。

#include<iostream>
    #include<set>
    
    #include<string.h>
    #include<algorithm>
    
    using namespace std;
    set<string> a;   // 胜利者集合 
    set<string> b;   // 失败者集合 
    int main()
    {
    	int n;
    	while(~scanf("%d",&n)&&n)
    	{
    		int f=0;
    		string s1,s2;
    		a.clear();
    		b.clear();
    		for(int i=0;i<n;i++)
    		{
    			cin>>s1>>s2;
    		    a.insert(s1);
    		    b.insert(s2);
    		}
    		for(set<string>::iterator it=b.begin();it!=b.end();)
    		{
    			if(a.count((*it)))
    			{
    				set<string>::iterator id=a.find(*it);
    				
    				it++;
    				a.erase(id);
    			}
    			else
    			it++;
    		}
    		if(a.size()==1)
    		printf("Yes\n");
    		else
    		printf("No\n");
    	}
    	return 0;
    }

[Easy_]: http://acm.hdu.edu.cn/search.php?field=problem&key=%D3%AD%BD%D3%D0%C2%D1%A7%C6%DA%A1%AA%A1%AA%B3%AC%BC%B6Easy%B0%E6%C8%C8%C9%ED%C8%FC&source=1&searchmode=source
[2093]: http://acm.hdu.edu.cn/showproblem.php?pid=2093
[1811]: http://acm.hdu.edu.cn/showproblem.php?pid=1811
[2086]: http://acm.hdu.edu.cn/showproblem.php?pid=2086
[3342]: http://acm.hdu.edu.cn/showproblem.php?pid=3342
[2647]: http://acm.hdu.edu.cn/showproblem.php?pid=2647