产生冠军

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 11417    Accepted Submission(s): 5286

3

Alice Bob

Smith John

Alice Smith

5

a c

c d

d e

b e

a d

0

Yes

No

Statistic | 

pid=2094" style="color:rgb(26,92,200); text-decoration:none">Submit | Discuss | Note

对于这道题 第一次我用的拓扑排序  但是。。

写着写着不知道怎样写下去了。

当sum>0的时候是信息冲突。出现两个入度同一时候为0的是信息不完整（对于推断整个排名，不不过冠军）

但是这道题推断的仅仅是冠军。不知道从何下手了。。

到最后还是百度了。

但是我看别人做的也是有错误的。。却能AC..可能是题目叙述不清的缘故把。对于网上的，假设1 2，2 3，4 5，5 6，6 4后者都成环了。。

还能推断冠军。

就这吧。。

我也不知道咋办了

AC:

#include <iostream>

#include <cstring>

#include <cstdio>

#include <set>

using namespace std;

int main()

{

    set<string>s1;

    set<string>s2;

    int n;

    while(~scanf("%d",&n))

    {

        if(n==0)

        break;

        char str1[50],str2[50];

        while(n--)

        {

            scanf("%s %s",str1,str2);

            s1.insert(str1);

            s1.insert(str2);

            s2.insert(str2);

            memset(str1,0,sizeof(str1));

            memset(str2,0,sizeof(str2));

        }

        if(s1.size()-s2.size()==1)

        printf("Yes\n");

        else

        printf("No\n");

        s1.clear();

        s2.clear();

    }

    return 0;

}

我的拓扑排序：不会了0.0是wa的：

#include <stdio.h>

#include <string.h>

#include <vector>

#include <queue>

using namespace std;

int vis[1005][1005],in[1005],k,sum;

vector<int>map[1005];

void top_sort()

{

	queue<int>s;

	for(int i=0;i<k;i++)

	if(in[i]==0)

	s.push(i);

	while(!s.empty())

	{

		if(s.size()>1)

		break;

		int pos=s.front();

		s.pop();

		sum--;

		for(int i=0;i<map[pos].size();i++)

		{

			in[map[pos][i]]--;

			if(in[map[pos][i]]==0)

			s.push(map[pos][i]);

		}

	}

	if(sum>0||!s.empty())//不会了0.0

	{

		printf("No\n");

		while(!s.empty())

		s.pop();

	}

	else

	printf("Yes\n");

}

int main()

{

	int n;

	char str[1005][50];

	while(scanf("%d",&n)&&n)

	{

		memset(str,0,sizeof(str));

		memset(vis,0,sizeof(vis));

		memset(map,0,sizeof(map));

		memset(in,0,sizeof(in));

		k=0;

		for(int i=0;i<n;i++)

		{

			int a=-1,b=-1;

			char str1[50],str2[50];

			memset(str1,0,sizeof(str1));

			memset(str2,0,sizeof(str2));

			scanf("%s %s",str1,str2);

			for(int j=0;j<k;j++)

			{

				if(strcmp(str1,str[j])==0)

				a=j;

				if(strcmp(str2,str[j])==0)

				b=j;

			}

			if(a==-1)

			strcpy(str[k++],str1),a=k-1;

			if(b==-1)

			strcpy(str[k++],str2),b=k-1;

			if(!vis[a][b])

			vis[a][b]=1,map[a].push_back(b),in[b]++;

		}

		sum=k;

		top_sort();

	}

	return 0;

}