学步园

代码抄自：hdu1811 - Ice_Crazy的专栏 - 博客频道 - CSDN.NET

题目大意：给你一些大小关系，让你判断是否能够使所有元素有序排列起来。如果可以输出OK，要是有冲突输出CONFLICT，在没有冲突的条件下如果关系不满足全部排序，输出UNCERTAIN。

Eage类中的from代表较大值x，to代表较小值y，next是x的下一个直接下属yi所组成的Eage在ee数组中的编号，next为-1时代表遍历完全所有的yi。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>

using namespace std;

const int maxn = 10010;
const int maxm = 20010;

int n, m;
int father[maxn], in[maxn], ans;
struct Eage
{
    int from, to, next;
}ee[maxm];

int head[maxn], a[maxm], b[maxm], tot;
char sh[maxm][4];

//x为较大值，y为较小值
void add(int x, int y)
{
    ee[tot].from = x;
    ee[tot].to = y;
    //上一次x作为较大值时所存边的编号
    ee[tot].next = head[x];
    head[x] = tot++;
}

int find_father(int k)
{
    if(father[k] == k)
        return k;
    return father[k] = find_father(father[k]);
}

int Get_Map()
{
    int fa, fb;
    for(int i = 0; i < n; i++)
        father[i] = i;
    for(int i = 0; i < m; i++)
    {
        scanf("%d%s%d", &a[i], sh[i], &b[i]);
        //相等合并为一点
        if(sh[i][0] == '=')
        {
            fa = find_father(a[i]);
            fb = find_father(b[i]);
            father[fb] = fa;
        }
    }
    memset(head, -1, sizeof(head));
    memset(in, 0, sizeof(in));
    //father数组一步到位
    for(int i = 0; i < n; i++)
        find_father(i);
    tot = 0;
    for(int i = 0; i < m; i++)
    {
        //并点后发现关系发生矛盾，直接输出矛盾
        if(father[a[i]] == father[b[i]] && sh[i][0] != '=')
            return 1;
        if(sh[i][0] == '>')
        {
            add(father[a[i]], father[b[i]]);
            in[father[b[i]]]++;
        }
        if(sh[i][0] == '<')
        {
            add(father[b[i]], father[a[i]]);
            in[father[a[i]]]++;
        }
    }
    return 0;
}

int Topsort()
{
    int flag, tmp, now, tot2;
    queue<int> q;

    tot = flag = tmp = 0;
    for(int i = 0; i < n; i++)
    {
        if(father[i] == i)
        {
            tot++;
            //入度为0，即rating最大的点，环上的点入度均不为0
            if(!in[i])
            {
                tmp++;
                q.push(i);
            }
            //rating最大的点不止一个，但还是有可能会有矛盾关系
            if(tmp > 1)
                flag = 2;
        }
    }

    int k = 0, v;
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        //记录有多少条合法边
        k++;
        in[now]--;
        tmp = 0;
        for(int j = head[now]; j != -1; j = ee[j].next)
        {
            v = ee[j].to;
            in[v]--;
            if(!in[v])
            {
                //直接下属不止一个，可能是不能确定，但也有可能剩下的关系会矛盾
                tmp++;
                //为了检测删点是否有环
                q.push(v);
            }
        }
        //删点之后剩余的rating最大点不止一个
        if(tmp > 1)
            flag = 2;
    }
    //合法边与总边数不等
    if(k < tot)
        flag = 1;
    return flag;
}

int main()
{
//    freopen("1811.in", "r", stdin);

    while(~scanf("%d%d", &n, &m))
    {
        ans = Get_Map();
        if(!ans)
            ans = Topsort();
        if(!ans)
            puts("OK");
        else if(ans == 1)
            puts("CONFLICT");
        else
            puts("UNCERTAIN");
    }

    return 0;
}