感觉这题的并查集以及拓扑排序并不难，但是做题的时候必须理解到矛盾(CONFLICT)与不确定(UNCERTAIN)直接的优先关系。

　　做这题的时候，构图什么的很简单，就是没有将矛盾摆在最高优先，一旦搜到不确定的情况就立即跳转，这是不对的。

代码如下：

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6   7 using namespace std;  8   9 const int N = 11111; 10 struct MFS { 11     int fa[N]; 12     void init() { for (int i = 0; i < N; i++) fa[i] = i;} 13     int find(int x) { return fa[x] = fa[x] == x ? x : find(fa[x]);} 14     void merge(int x, int y) { 15         int fx = find(x), fy = find(y); 16         if (fx == fy) return ; 17         fa[fx] = fy; 18     } 19 } mfs; 20  21 int x[N << 1], y[N << 1], inarc[N]; 22 bool used[N]; 23 char op[N << 1][3]; 24  25 struct Edge { 26     int t, nx; 27     Edge() {} 28     Edge(int t, int nx) : t(t), nx(nx) {} 29 } edge[N << 1]; 30 int eh[N], ec; 31  32 void init() { 33     mfs.init(); 34     memset(used, 0, sizeof(used)); 35     memset(inarc, 0, sizeof(inarc)); 36     memset(eh, -1, sizeof(eh)); 37     ec = 0; 38 } 39  40 void addedge(int s, int t) { 41     edge[ec] = Edge(t, eh[s]); 42     eh[s] = ec++; 43 } 44  45 typedef pair
           
             PII; 46 set
            
              nodes; 47 48 void input(int n, int m) { 49 init(); 50 for (int i = 0; i < m; i++) { 51 scanf("%d%s%d", &x[i], op[i], &y[i]); 52 if (op[i][0] == '=') mfs.merge(x[i], y[i]); 53 else if (op[i][0] == '<') inarc[x[i]]++; 54 else if (op[i][0] == '>') inarc[y[i]]++; 55 } 56 for (int i = 0; i < n; i++) { 57 int rt = mfs.find(i); 58 used[rt] = true; 59 if (rt != i) inarc[rt] += inarc[i]; 60 } 61 // for (int i = 0; i < n; i++) { 62 // if (!vis[i]) continue; 63 // cout << i << '~' << inarc[i] << ": "; 64 // for (int t = eh[i]; ~t; t = edge[t].nx) cout << edge[t].t << ' '; 65 // cout << endl; 66 // } 67 } 68 69 int topo(int n, int m) { 70 for (int i = 0; i < m; i++) { 71 if (op[i][0] == '<') { 72 if (mfs.fa[x[i]] == mfs.fa[y[i]]) return -2; 73 addedge(mfs.fa[y[i]], mfs.fa[x[i]]); 74 } 75 if (op[i][0] == '>') { 76 if (mfs.fa[x[i]] == mfs.fa[y[i]]) return -2; 77 addedge(mfs.fa[x[i]], mfs.fa[y[i]]); 78 } 79 } 80 nodes.clear(); 81 for (int i = 0; i < n; i++) if (used[i]) nodes.insert(PII(inarc[i], i)); 82 PII tmp; 83 bool unc = false; 84 while (!nodes.empty()) { 85 tmp = *nodes.begin(); 86 // cout << tmp.first << ' ' << tmp.second << endl; 87 nodes.erase(nodes.begin()); 88 if (tmp.first) return -2; 89 if (!nodes.empty() && (*nodes.begin()).first == 0) unc = true; 90 for (int t = eh[tmp.second]; ~t; t = edge[t].nx) { 91 int id = edge[t].t; 92 if (inarc[id] < 0) { 93 cout << "shit!" << endl; 94 while (1) ; 95 } 96 nodes.erase(PII(inarc[id], id)); 97 nodes.insert(PII(--inarc[id], id)); 98 } 99 }100 return unc;101 }102 103 int main() {104 // freopen("in", "r" ,stdin);105 int n, m;106 while (~scanf("%d%d", &n, &m)) {107 input(n, m);108 int ans = topo(n, m);109 // cout << ans << endl;110 if (ans == 0) puts("OK");111 else if (ans == 1) puts("UNCERTAIN");112 else puts("CONFLICT");113 }114 return 0;115 }
            
           
          
         
        
       
      

 

——written by Lyon