rank of tetris(拓扑排序＋集合).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define NMAX 10010
int degre[NMAX]; 
int eq[NMAX];
int n,m;
vector< vector<int> > path;
queue< int > SQ;
bool is_conf, is_uncer;

void top_sort()
{
	int now,l,i;
	
	while (!SQ.empty()) {
		l = SQ.size();
		if (l > 1) {
			is_uncer = true;
		}
		now = SQ.front();
		SQ.pop();
		degre[now] = -1;
		l = path[now].size();
		for (i=0;i<l;i++) {
			int next = path[now][i];
			while (eq[next] != -1) {
				next = eq[next];
			}
			degre[next] --;
			if (degre[next] == 0) {
				SQ.push(next);
			}
		}
	}
}

int main()
{
	int i,j,l;
	int x,y;
	char op;
	
	while (scanf("%d %d",&n,&m)==2) {
		memset(degre,0,sizeof(degre));
		memset(eq,-1,sizeof(eq));
		path.resize(n+10);
		is_conf = is_uncer = false;
		for (i=0;i<=n;i++) {
			path[i].clear();
		}
		i = SQ.size();
		while (i --) {
			SQ.pop();
		}
		for (i=0;i<m;i++) {
			scanf("%d %c %d",&x,&op,&y);
			if (op == '>') {
				while (eq[x] != -1) {
					x = eq[x];
				}
				while (eq[y] != -1) {
					y = eq[y];
				}
				if (x == y) {
					is_conf = true;
				}
				degre[y] ++;
				path[x].push_back(y);
			}
			else if (op == '<') {
				while (eq[x] != -1) {
					x = eq[x];
				}
				while (eq[y] != -1) {
					y = eq[y];
				}
				if (x == y) {
					is_conf = true;
				}
				degre[x] ++;
				path[y].push_back(x);
			}
			else {
				while (eq[x] != -1) {
					x = eq[x];
				}
				while (eq[y] != -1) {
					y = eq[y];
				}
				if (x == y) {
					continue ;
				}
				degre[x] += degre[y];
				eq[y] = x;
				l = path[y].size();
				for (j=0;j<l;j++) {
					path[x].push_back( path[y][j] );
				}
			}
		}
		
		for (i=0;i<n;i++) {
			if (eq[i] == -1 && degre[i] == 0) {
				SQ.push(i);
			}
		}
		
		if (is_conf) {
			puts("CONFLICT");
			continue ;
		}
		top_sort();			
		for (i=0;i<n;i++) {
			if (eq[i] == -1 && degre[i] > 0) {
				break ;
			}
		}
		if (i != n) {
			is_conf = true;
		}
		if (is_conf) {
			puts("CONFLICT");
		}
		else if (is_uncer) {
			puts("UNCERTAIN");
		}
		else {
			puts("OK");
		}
	}
}