1943.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1943 on 2006-01-29 at 13:38:31 */ 
#include <cstdio>
#include <cstring>

const int MAX = 512;

class Group {
public:
	int con[MAX], number;
	void add(int i) {
		con[number++] = i;
	}
};

class Graph {
private:
	int stack[MAX], top;
public:
	int m[MAX][MAX];
	int ingroup[MAX], indeg[MAX], gnum;
	Group g[MAX];
	void fillGroup(const int N) {
		int i, j;
		memset(ingroup, -1, sizeof(ingroup));
		memset(indeg, 0, sizeof(indeg));
		top = gnum = 0;
		for(i = 1; i <= N; i++) g[i].number = 0;
		for(i = 1; i <= N; i++) {
			if(ingroup[i] == -1) {
				stack[top++] = i;
				ingroup[i] = ++gnum;
				g[gnum].add(i);
				while(top > 0) {
					int t = stack[--top];
					for(j = 1; j <= N; j++) {
						if(m[t][j] == 2 && ingroup[j] == -1) {
							g[gnum].add(j);
							ingroup[j] = ingroup[t];
							stack[top++] = j;
						}
						if(m[j][t] == 1) indeg[ingroup[t]]++;
					}
				}
			}
		}
	}
	bool haveCircle(const int N) {
		int i, j;
		bool inStack[MAX];
		top = 0;
		memset(inStack, false, sizeof(inStack));
		while(true) {
			for(i = 1; i <= gnum; i++) {
				if(indeg[i] == 0 && !inStack[i]) {
					stack[top++] = i;
					inStack[i] = true;
				}
			}
			if(top == 0) {
				for(i = 1; i <= gnum; i++)
					if(!inStack[i]) return true;
				return false;
			} else {
				int t = stack[--top];
				for(i = 0; i < g[t].number; i++)
					for(j = 1; j <= N; j++)
						if(m[g[t].con[i]][j] == 1) indeg[ingroup[j]]--;
			}    
		}    
	}
};

void scanBigger(int&, int&);
void scanEqual(int&, int&);
bool superp(const Graph&, const Graph&);

Graph x, y;
bool wrong;

int main()
{
	int t, T, i, N, M;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d", &N, &M);
		wrong = false;
		memset(x.m, 0, sizeof(x.m));
		memset(y.m, 0, sizeof(y.m));
		for(i = 0; i < M; i++) {
			int a, b; char R[8];
			scanf("%d %s %d", &a, R, &b);
			if(a == b) wrong = true;
			if(!strcmp(R, "E")) {
				scanBigger(x.m[b][a], x.m[a][b]);
				scanEqual(y.m[a][b], y.m[b][a]);
			} else if(!strcmp(R, "S")) {
				scanEqual(x.m[a][b], x.m[b][a]);
				scanBigger(y.m[a][b], y.m[b][a]);
			} else if(!strcmp(R, "W")) {
				scanBigger(x.m[a][b], x.m[b][a]);
				scanEqual(y.m[a][b], y.m[b][a]);
			} else if(!strcmp(R, "N")) {
				scanEqual(x.m[a][b], x.m[b][a]);
				scanBigger(y.m[b][a], y.m[a][b]);
			} else if(!strcmp(R, "SE")) {
				scanBigger(x.m[b][a], x.m[a][b]);
				scanBigger(y.m[a][b], y.m[b][a]);
			} else if(!strcmp(R, "NE")) {
				scanBigger(x.m[b][a], x.m[a][b]);
				scanBigger(y.m[b][a], y.m[a][b]);
			} else if(!strcmp(R, "SW")) {
				scanBigger(x.m[a][b], x.m[b][a]);
				scanBigger(y.m[a][b], y.m[b][a]);
			} else if(!strcmp(R, "NW")) {
				scanBigger(x.m[a][b], x.m[b][a]);
				scanBigger(y.m[b][a], y.m[a][b]);
			}
		}
		if(wrong) printf("IMPOSSIBLE\n");
		else {
			x.fillGroup(N); y.fillGroup(N);
			if(superp(x, y) || x.haveCircle(N) || y.haveCircle(N)) printf("IMPOSSIBLE\n");
			else printf("POSSIBLE\n"); 
		}
	}

	return 0;
}

void scanBigger(int& a, int& b)
{
	if(a == 0) a = 1, b = -1;
	else if(a != 1) wrong = true;
}
void scanEqual(int& a, int& b)
{
	if(a == 0) b = a = 2;
	else if(a != 2) wrong = true;
}
bool superp(const Graph& x, const Graph& y)
{
	int i, j, k;
	for(i = 1; i <= x.gnum; i++)
		for(j = 0; j < x.g[i].number; j++)
			for(k = j+1; k < x.g[i].number; k++)
				if(y.ingroup[x.g[i].con[j]] == y.ingroup[x.g[i].con[k]])
					return true;
	return false;
}