拓扑排序和并查集的结合
拓扑排序来进行排序
如果同时出现了两个以上的节点入度为0，代表这几个节点的顺序是不确定的也就是信息不完善
如果最后出现了有些节点的入度不是零，说明存在了环，也就是出现了冲突
并查集把相等的节点归并到一个集合，可以把多个节点当成一个节点来处理
#include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> using namespace std; const int maxn = 10000 + 10; int n, m, N; int p[maxn]; int in[maxn]; vector<int> vec[maxn]; struct str{ int a, b; char c; }e[maxn*2]; int tofind(int x){ if(x == p[x]) return x; return p[x] = tofind(p[x]); } init(){ for(int i = 0; i < N; i++){ p[i] = i; in[i] = 0; vec[i].clear(); } } void solve(){ queue<int> q; for(int i = 0; i < N; i++){ if(!in[i] && p[i] == i){ q.push(i); } } bool bug = false; while(!q.empty()){ int t = q.front(); q.pop(); if(!q.empty()){ bug = true; } for(auto &y : vec[t]){ in[y]--; if(!in[y]){ q.push(y); } } n--; } if(n) printf("CONFLICT\n"); else if(bug) printf("UNCERTAIN\n"); else printf("OK\n"); } int main(){ int a, b; char c; int fa, fb; while(scanf("%d%d", &n, &m) != EOF){ N = n; init(); for(int i = 0; i < m; i++){ // cin>>e[i].a>>e[i].c>>e[i].b; scanf("%d %c %d", &e[i].a, &e[i].c, &e[i].b); if(e[i].c == '='){ fa = tofind(e[i].a); fb = tofind(e[i].b); if(fa != fb){///如果前面已经judge过 fa==fb 不需要再重复 p[fa] = fb; n--; } } } for(int i = 0; i < m; i++){ if(e[i].c == '=') continue; fa = tofind(e[i].a); fb = tofind(e[i].b); if(e[i].c == '>'){ vec[fb].push_back(fa); in[fa]++; } else{ vec[fa].push_back(fb); in[fb]++; } } solve(); } return 0; }