不熟悉的点：

1.并查集的按秩压缩

2.vector建图

3.bfs拓扑排序

 

1 #include "cstdio" 2 #include "iostream" 3 #include "cstring" 4 #include "vector" 5 #include "queue" 6 using namespace std; 7 const int N = 10005; 8 int n, m, t; 9 int fa[N];10 int X[2 * N], Y[2 * N];11 int son[N];12 char O[2 * N];13 vector
     
      G[N];14 15 void init(int n)16 {17     for (int i = 0; i <= n; ++i)18         fa[i] = -1;19     for (int i = 0; i <= n; ++i)20         G[i].clear();21     memset(son, 0, sizeof(son));22 }23 int find(int x)24 {25     if (fa[x] < 0) return x;26     return fa[x] = find(fa[x]);27 }28 29 bool merg(int a, int b)30 {31     int x = find(a);32     int y = find(b);33     if (x == y) return false;34     else if (x < y){35         fa[x] += fa[y];36         fa[y] = x;37     }38     else {39         fa[y] += fa[x];40         fa[x] = y;41     }42     return true;43 }44 45 int main()46 {47     while (cin >> n >> m) {48         init(n);49         int num = n;50         for (int i = 0; i < m; ++i) {51             cin >> X[i] >> O[i] >> Y[i];52             if (O[i] == '=') {53                 if (merg(X[i], Y[i]))54                     num--;55             }56         }57         for (int i = 0; i < m; ++i) if (O[i] != '=') {58             int x = find(X[i]);59             int y = find(Y[i]);60             if (O[i] == '>') {61                 G[x].push_back(y);62                 son[y]++;63             }64             else {65                 G[y].push_back(x);66                 son[x]++;67             }68         }69         queue
      
        q;70         for (int i = 0; i < n; ++i)71             if (son[i] == 0 && i == find(i))72                 q.push(i);73         int sin = 0;74         while (!q.empty()) {75             if (q.size() > 1) sin = 1;76             int t = q.front();77             q.pop();78             --num;79             for (int v = 0; v < G[t].size(); ++v) {80                 if (--son[G[t][v]] == 0)81                     q.push(G[t][v]);82             }83         }84         if (num > 0) cout << "CONFLICT" << endl;85         else if (sin) cout << "UNCERTAIN" << endl;86         else cout << "OK" << endl;87     }88     return 0;89 }