并查集+拓扑排序
把等号的那些东西都用并查集合并一下，这样一来，建立邻接表的时候用根来建立就好了。
然后就是拓扑排序。
如果有两个入度为0的节点，那么说明肯定是条件不足，
如果有成环的肯定是没法排序了。
#include#include #include #include #include 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 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\n"); else if (jieguo == 2) printf("CONFLICT\n"); else if (jieguo == 3) printf("UNCERTAIN\n"); } return 0;}