ACMclub - 2131 产生冠军（拓扑排序，map）

本文主要是介绍ACMclub - 2131 产生冠军（拓扑排序，map），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接

1、成环矛盾

2、不全在同一集合则无法产生冠军。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
using namespace std;
int N, M;
const int MAXN = 1001, MAXM = MAXN*MAXN/2;
int g[MAXN][MAXN], in[MAXN],  ans[MAXN];
typedef map<string, int> P;
int fa[MAXN];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]);}
void unite(int x, int y) { x = find(x), y = find(y), fa[x] = y;}
int topoSort()
{int in1[MAXN];for(int i = 1; i <= N; i++) in1[i] = in[i];for(int k = 0; k < N; k++){int i = 1;while(in1[i]!=0){i++;if(i > N)return 2;	//成环，矛盾}ans[k] = i;in1[i]--;for(int j = 1; j <= N; j++)if(g[i][j])in1[j]--;}fa[1] = find(fa[1]);for(int i = 1; i <= N; i++)if(fa[1] != find(fa[i]))return 1;return 0;			//确定排序
}
int main()
{//freopen("in.txt", "r", stdin);while(scanf("%d",&M)!=EOF && M){P p;for(int i = 1; i <= MAXN; i++) fa[i]  = i;N = 0;memset(g, 0, sizeof(g));memset(in, 0, sizeof(in));for(int i = 0; i < M; i++){char u[100], v[100];scanf("%s%s", &u, &v);if(!p[u])p[u] = ++N;if(!p[v])p[v] = ++N;unite(p[u], p[v]);g[p[u]][p[v]] = 1;in[p[v]]++;}printf(topoSort()? "No\n" : "Yes\n");}return 0;
}

这篇关于ACMclub - 2131 产生冠军（拓扑排序，map）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---