好题。

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

分析：

 

#include <bits/stdc++.h>

using namespace std;
const int N = 10010;


vector<int> mp[N];
int vis[N];
int a[N*2], b[N*2]; // 记录输入的关系
char ch[N*2];
int n, m;
int cnt = 0;    // 记录合并后剩余点的个数

int pre[N], id[N];  // id 是合并后剩余的点
int find(int x)
{
    if(x == pre[x])
        return x;
    return pre[x] = find(pre[x]);
}

// 返回0 conflict 返回1 uncertain
int topo_sort()
{
    int point = cnt;    // 剩余点的个数，判断
    int uncertain = 0;
    priority_queue<int, vector<int>, greater<int> > que;
    for(int i=0; i<cnt; i++)
    {
        if(vis[id[i]] == 0)
            que.push(id[i]);
    }

    while(!que.empty())
    {
        if(que.size() > 1)  uncertain = 1;  // 如果一次队列里有两个点，说明肯定有两个点的关系不能确定，信息不全
        int v = que.top();  que.pop();
        point --;
        for(int i=0; i<mp[v].size(); i++)
        {
            vis[find(mp[v][i])] --;
            if(vis[find(mp[v][i])] == 0)
                que.push(find(mp[v][i]));
        }
    }
    if(point > 1)       return 0;   // 如果大于1 说明有环，因为有环至少剩两个点 conflict
    else if(uncertain)  return 1;
    else                return 2;
}

int main()
{
    while(scanf("%d %d%*c", &n, &m) != EOF)
    {
        for(int i=0; i<N; i++)  mp[i].clear();
        for(int i=0; i<N; i++)  vis[i] = 0, pre[i] = i;

        for(int i=0; i<m; i++)
        {
            scanf("%d %c %d%*c", &a[i], &ch[i], &b[i]);
            if(ch[i] == '=')
            {
                int fa = find(a[i]);
                int fb = find(b[i]);
                if(fa != fb)
                    pre[fa] = fb;
            }
        }
        int conflict = 0;
        for(int i=0; i<m; i++)
        {
            if(ch[i] == '=')    continue;
            int fa = find(a[i]);
            int fb = find(b[i]);
            if(fa == fb)    // 前面输入得时候已经相等得合并了，如果除了相等还出现 > < 情况就冲突
            {
                conflict = 1;
                break;
            }

            if(ch[i] == '>')
            {
                mp[fa].push_back(fb);
                vis[fb]++;
            }
            else if(ch[i] == '<')
            {
                mp[fb].push_back(fa);
                vis[fa] ++;
            }
        }
        if(conflict)    // 如果是冲突的话直接输出
        {
            printf("CONFLICT\n");
            continue;
        }
        
        cnt = 0;    // 记录合并后剩余点的个数
        for(int i=0; i<n; i++)  // 统计剩余的点
        {
            if(pre[i] == i)
                id[cnt++] = i;
        }
        
        int ans = topo_sort();
        if(ans == 0)        printf("CONFLICT\n");
        else if(ans == 1)   printf("UNCERTAIN\n");
        else                printf("OK\n");
    }


    return 0;
}