题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1811

求一堆数据的拓扑序。

处理:x>y就是x到y一条边,x<y就是y到x一条边。关键问题是处理x=y的情况。

假如x=y,就有问题了。假如不处理的话,可能会被当成少处理一个点而使结果编程UNCERTAIN。所以我们考虑用并查集来解决这个问题。

选谁当祖先?题中又给了一个其他的量叫做RP值,这个RP值的规律是序号越大RP值越大。这样我们可以在合并的时候,尽可能地将RP值大的数当成本集合的祖先。

 /*
━━━━━┒ギリギリ♂ eye!
┓┏┓┏┓┃キリキリ♂ mind!
┛┗┛┗┛┃\○/
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define fr first
#define sc second
#define cl clear
#define BUG puts("here!!!")
#define W(a) while(a--)
#define pb(a) push_back(a)
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%lld", &a)
#define Rs(a) scanf("%s", a)
#define Cin(a) cin >> a
#define FRead() freopen("in", "r", stdin)
#define FWrite() freopen("out", "w", stdout)
#define Rep(i, len) for(int i = 0; i < (len); i++)
#define For(i, a, len) for(int i = (a); i < (len); i++)
#define Cls(a) memset((a), 0, sizeof(a))
#define Clr(a, x) memset((a), (x), sizeof(a))
#define Full(a) memset((a), 0x7f7f, sizeof(a))
#define lp p << 1
#define rp p << 1 | 1
#define pi 3.14159265359
#define RT return
#define lowbit(x) x & (-x)
#define onenum(x) __builtin_popcount(x)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef map<string, int> msi;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb; typedef struct Edge {
int u, v, next;
Edge() {}
Edge(int uu, int vv) : u(uu), v(vv) { next = -; }
}Edge;
const int maxn = ;
const int maxm = ;
int n, m;
Edge edge[maxm];
int head[maxn];
int hcnt;
int pre[maxn];
int in[maxn];
int num, q[maxn], front, tail;
int uu[maxn], vv[maxn];
char cc[maxn][]; void adde(int u, int v) {
edge[hcnt] = Edge(u, v);
edge[hcnt].next = head[u];
head[u] = hcnt++;
in[v]++;
} int find(int x) {
RT x == pre[x] ? x : pre[x] = find(pre[x]);
} int unite(int x, int y) {
int fx = find(x);
int fy = find(y);
if(fx == fy) RT ;
if(x > y) pre[fy] = fx;
else pre[fx] = fy;
return ; } int topo() {
front = tail = ;
Rep(i, n) {
if(in[i] == && i == find(i)) {
q[tail++] = i;
}
}
int ret = ;
while(front < tail) {
if(tail - front > ) ret = ;
int u = q[front++];
--num;
for(int i = head[u]; ~i; i=edge[i].next) {
int v = edge[i].v;
if(--in[v] == ) {
q[tail++] = v;
}
}
}
if(num > ) printf("CONFLICT\n");
else if(ret) printf("UNCERTAIN\n");
else printf("OK\n");
} int main() {
// FRead();
int u, v;
while(~Rint(n) && ~Rint(m)) {
Cls(in); Clr(head, -); hcnt = ;
num = n;
Rep(i, n+) pre[i] = i;
Rep(i, m) {
Rint(uu[i]); Rs(cc[i]); Rint(vv[i]);
if(cc[i][] == '=') {
if(unite(uu[i], vv[i])) num--;
}
}
Rep(i, m) {
if(cc[i][] != '=') {
u = find(uu[i]); v = find(vv[i]);
if(cc[i][] == '>') adde(u, v);
if(cc[i][] == '<') adde(v, u);
}
}
topo();
}
RT ;
}

最新文章

  1. Alpha阶段冲刺项目总结(补充)
  2. 点击按钮对两个div的隐藏与显示进行切换
  3. javascript中的后退和刷新
  4. [动态规划]状态压缩DP小结
  5. [HIHO]hihoCoder太阁最新面经算法竞赛7
  6. IOS 系统API---NSJSONSerialization四个枚举什么意思
  7. javascript笔记02:严格模式的特定要求
  8. HDU 1560 DNA sequence (IDA* 迭代加深 搜索)
  9. 开发错误日志之Unix/Linux命令未执行或无结果等且程序无错误
  10. 从Ueditor跨域上传,总结的一次跨域上传的爬坑经历
  11. asm_c515c.uew
  12. 将Eclipse代码导入到Android Studio的两种方式
  13. #include &lt;iostream&gt;
  14. 一步一步学MySQL-一致性非锁定读和锁定读
  15. maven快速下载jar镜像
  16. 基于jeesite的cms系统(三):使用RESTful API在前端渲染数据
  17. js中函数创建的三种方式
  18. C语言列出真分数序列代码及解析
  19. ElasticSearch(二):允许外网连接服务配置
  20. 【开源】Skatch 正式发布 - 极速渲染抽象派草图

热门文章

  1. bnuoj 33647 Angry Grammar Nazi(字符串)
  2. 如何阻止iframe里引用的网页自动跳转
  3. Oracle 删除表分区
  4. VMware ESXi虚拟机克隆及迁移
  5. SQL SERVER时间函数
  6. 如何通过CSS3实现背景图片色彩的梯度渐变
  7. 阿里云CentOS6.3 安装MongoDB教程
  8. PHP之set_error_handler()函数讲解
  9. span标签里的内容在IE下显示,而在谷歌浏览器下不显示
  10. POJ 1026 Cipher(置换群)