3 3 0 > 1 1 < 2 0 > 2 4 4 1 = 2 1 > 3 2 > 0 0 > 1 3 3 1 > 0 1 > 2 2 < 1
OK CONFLICT UNCERTAIN
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <vector> using namespace std; int fa[10005]; int inde[10005]; int a[20005]; int b[20005]; char c[20005]; vector<int>edge[10005]; int n , m , sum; void init() { sum = n; for(int i = 0; i < n; i ++) { inde[i] = 0; fa[i] = i ; edge[i].clear(); } } int find_fa(int x) { if(x == fa[x]) return x; return fa[x] = find_fa(fa[x]); } void union_ab(int x , int y) { x = find_fa(x); y = find_fa(y); if(x == y) return ; fa[x] = y; } void to_sort() { queue<int>q; for(int i = 0; i < n; i ++) { if(inde[i] == 0 && fa[i] == i) q.push(i); } int u ; int flag = 0; while(!q.empty()) { if(q.size() > 1) flag = 1; u = q.front(); q.pop(); sum --; for(int i = 0; i < (int)edge[u].size(); i ++) { if(--inde[edge[u][i]] == 0) q.push(edge[u][i]); } } if(sum > 0) printf("CONFLICT\n"); else if(flag) printf("UNCERTAIN\n"); else printf("OK\n"); } int main() { int fx , fy ; while(scanf("%d %d",&n ,&m)!=EOF) { init(); for(int i = 0; i < m; i ++) { scanf("%d %c %d",&a[i],&c[i],&b[i]); if(c[i] == ‘=‘) { fx = find_fa(a[i]); fy = find_fa(b[i]); if(fx != fy){ union_ab(a[i] , b[i]); sum --; } } } for(int i = 0; i < m; i ++) { if(c[i] != ‘=‘) { fx = find_fa(a[i]); fy = find_fa(b[i]); if(c[i] == ‘>‘){ edge[fx].push_back(fy); inde[fy] ++; } else{ edge[fy].push_back(fx); inde[fx] ++; } } } to_sort(); } return 0; }
Rank of Tetris (拓扑 + 并查集),布布扣,bubuko.com
原文:http://blog.csdn.net/wuhuajunbao/article/details/23126593