并查集+拓扑排序
把等号的那些东西都用并查集合并一下，这样一来，建立邻接表的时候用根来建立就好了。
然后就是拓扑排序。
如果有两个入度为0的节点，那么说明肯定是条件不足，
如果有成环的肯定是没法排序了。
#include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> using namespace std; const int maxn = 10010; const int maxnn = 20010; int u[maxnn], v[maxnn], s[maxnn][2]; int father[maxn], rudu[maxn], ff[maxn], yy[maxn]; vector<int>ljb[maxn]; int find(int x) { while (father[x] != x) x = father[x] = father[father[x]]; return father[x]; } int main() { int n, m, i, ii, j; while (~scanf("%d%d", &n, &m)) { int jieguo = 1; for (i = 0; i <= n; i++) father[i] = i; memset(rudu, 0, sizeof(rudu)); memset(ff, 0, sizeof(ff)); for (i = 0; i <= n; i++) ljb[i].clear(); for (i = 0; i < m; i++) scanf("%d%s%d", &u[i], s[i], &v[i]); for (i = 0; i < m; i++) { if (s[i][0] == '=') { int fu = find(u[i]); int fv = find(v[i]); father[fu] = fv; } } int tott = 0; for (i = 0; i < n; i++) { int gen = find(i); if (ff[gen] == 0){ yy[tott] = gen; tott++; ff[gen] = 1; } } for (i = 0; i < m; i++) { if (s[i][0] == '>') { int fu = find(u[i]); int fv = find(v[i]); ljb[fu].push_back(fv); rudu[fv]++; } else if (s[i][0] == '<') { int fu = find(u[i]); int fv = find(v[i]); ljb[fv].push_back(fu); rudu[fu]++; } } int summ, r, cun[maxn], tongji = 0; while (1) { if (tongji == tott) break; summ = 0; for (i = 0; i < tott; i++) if (rudu[yy[i]] == 0) cun[summ] = yy[i], summ++, r = yy[i]; if (summ !=0) { tongji = tongji + summ; if (summ >= 2)jieguo = 3; for (i = 0; i < summ; i++) { rudu[cun[i]]--; for (j = 0; j < ljb[cun[i]].size(); j++) rudu[ljb[cun[i]][j]]--; } } if (summ == 0){ jieguo = 2; break; } } if (jieguo == 1) printf("OK "); else if (jieguo == 2) printf("CONFLICT "); else if (jieguo == 3) printf("UNCERTAIN "); } return 0; }