http://acm.hdu.edu.cn/showproblem.php?pid=1811

 #include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
const int N=;
vector<int>V[N];
queue<int>q;
char oper[N];
int in[N],f[N];
int a[N],b[N];
int n,m,sum;
void init()
{
sum = n;
while(!q.empty()) q.pop();
for (int i = ; i <= n; i++)
{
f[i] = i;
in[i] = ;
V[i].clear();
}
}
int Find(int x)
{
if(x!=f[x]) return f[x]=Find(f[x]);
return x;
}
int Merge(int x,int y)
{
x = Find(x);
y = Find(y);
if(x!=y)
{
f[y] = x;
return ;
}
return ;
}
void toposort()
{
int flag = ;
for (int i = ; i < n; i++)
{
if(in[i]==&&Find(i)==i)
q.push(i);
}
while(!q.empty())
{
if (q.size()>)flag = ;
int u = q.front();
q.pop();
sum--;
for (int i = ; i < V[u].size(); i++)
{
if(--in[V[u][i]]==)
q.push(V[u][i]);
}
}
if (sum > ) printf("CONFLICT\n");
else if (flag) printf("UNCERTAIN\n");
else printf("OK\n");
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
int u,v;
for (int i = ; i < m; i++)
{
scanf("%d %c %d",&a[i],&oper[i],&b[i]);
if(oper[i]=='=')
{
if(Merge(a[i],b[i]))
sum--;
}
}
for (int i = ; i < m; i++)
{
if(oper[i]=='=') continue;
u = Find(a[i]);
v = Find(b[i]);
if(oper[i]=='>')
{
V[u].push_back(v);
in[v]++;
}
if(oper[i]=='<')
{
V[v].push_back(u);
in[u]++;
}
}
toposort();
}
return ;
}

最新文章

  1. 使用VirtualBox自带管理工具命令为虚拟磁盘扩展空间
  2. Sqli-LABS通关笔录-13
  3. android6.0 适配的问题——activity销毁的问题
  4. assertThat用法
  5. linux下gcc编译多个源文件、gdb的使用方法
  6. eWebeditor编辑器上传图片路径错误解决方法[疑难杂症]【转,作者:unvs】
  7. screenX clientX pageX的区别
  8. 网站注册(css)
  9. 关于EL表达式的大小写问题。谁来帮我解答?
  10. 纯windows下制作变色龙引导安装U盘教程
  11. 查看Android数据库文件
  12. css绘制倒三角
  13. hibernate之Session对象
  14. Tomcat Getshell
  15. Day 6-1计算机网络基础&amp;TCP/IP
  16. VMWare安装CentOS 6.5图解
  17. 【剑指offer】数组中出现次数超过一半的数字
  18. UVa 548 Tree(二叉树最短路径)
  19. Scrapy的安装和基本使用方法
  20. MariaDB数据表操作实例

热门文章

  1. python3.x Day3 集合
  2. linux ifstat-统计网络接口流量状态
  3. C++ &lt;queue&gt;用法
  4. 利用 Python 批量修改文件名
  5. python经典书籍:Python编程实战 运用设计模式、并发和程序库创建高质量程序
  6. 在mac上面运行cherrytree
  7. gnuplot examples
  8. Leetcode 123.买卖股票的最佳时机III
  9. D - Doing Homework 状态压缩 DP
  10. - &gt; 并查集+路径压缩(详解)(第一节)