站外题求条

高手榜

题目描述:

自从Lele开发了Rating系统，他的Tetris事业更是如虎添翼，不久他便把这个游戏推向了全球。

为了更好的符合那些爱好者的喜好，Lele又想了一个新点子：他将制作一个全球Tetris高手排行榜，定时更新，名堂要比福布斯富豪榜还响。关于如何排名，这个不用说都知道是根据Rating从高到低来排，如果两个人具有相同的Rating，那就按这几个人的RP从高到低来排。

终于，Lele要开始行动了，对N个人进行排名。为了方便起见，每个人都已经被编号，分别从0到N-1,并且编号越大，RP就越高。同时Lele从狗仔队里取得一些（M个）关于Rating的信息。这些信息可能有三种情况，分别是"A > B","A = B","A < B"，分别表示A的Rating高于B, 等于B, 小于B。

现在Lele并不是让你来帮他制作这个高手榜，他只是想知道，根据这些信息是否能够确定出这个高手榜，是的话就输出"OK"。否则就请你判断出错的原因，到底是因为信息不完全（输出"UNCERTAIN"），还是因为这些信息中包含冲突（输出"CONFLICT"）。注意，如果信息中同时包含冲突且信息不完全，就输出"CONFLICT"。

输入格式:

测试第一行包含两个整数N,M(0<=N<=10000,0<=M<=20000)，分别表示要排名的人数以及得到的关系数。接下来有M行，分别表示这些关系。

输出格式:

第一行里按题目要求输出。

样例输入:

3 3
0 > 1
1 < 2
0 > 2

样例输出:

提示:

算法提示：并查集缩点 + 拓扑排序

时间限制: 1000ms
空间限制: 256MB
本蒟蒻50分代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define N 10001
int n, m;
string s;
vector<int>e[N], f;
queue<int>q;
int fa[N], ind[N];
int find(int x) {
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) fa[i] = i;
	cin >> s;
	for (int i = 1; i <= m; i++) {
		getline(cin, s);
		int x = s[0] - '0' + 1, y = s[4] - '0' + 1;
		int rx = find(x), ry = find(y);
		if (s[2] == '>') {
			e[rx].push_back(ry);
			ind[ry]++;
		} else if (s[2] == '=') {
			if (rx != ry) {
				fa[rx] = ry;
				ind[ry] += ind[rx];
				for (auto i : e[rx]) if (find(e[ry].begin(), e[ry].end(), i) == e[ry].end()) e[ry].push_back(i);
			}
		} else {
			e[ry].push_back(rx);
			ind[rx]++;
		}
	}
	for (int i = 1; i <= n; i++) if (!ind[i] && find(i) == i) q.push(i);
	int cnt=n;
	for (int i = 1; i <= cnt; i++) if (fa[i] != i) n--;
	bool b = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (!q.empty()) b = 0;
		f.push_back(x);
		for (auto j : e[x]) {
			ind[j]--;
			if (!ind[j] && fa[j] == j) q.push(j);
		}
	}
	if (f.size() == n && b) cout << "OK";
	else if (f.size() != n && b) cout << "CONFLICT";
	else if (f.size() == n && !b) cout << "UNCERTAIN";
	else cout << "CONFLICT";
	return 0;
}

讨论操作

高手榜