2021.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2021 on 2005-12-18 at 18:55:52 */ 
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

const int L_MAX = 32;
const int MAX = 256000;

class UFSet {
public:
	int parent[MAX];
	void makeSet();
	int find(int);
	void unionSet(int, int);
};
void UFSet::makeSet() {
	memset(parent, -1, sizeof(parent));
}
int UFSet::find(int x) {
	if(parent[x] == -1) {
		return x;
	} else {
		parent[x] = find(parent[x]);
		return parent[x];
	}
}
void UFSet::unionSet(int x, int y) {
	int pX = find(x);
	int pY = find(y);
	if(pX != pY) {
		parent[pX] = pY;
	}
}

class Color {
public:
	char name[L_MAX];
	int d;
	void clear(const Color&);
};
void Color::clear(const Color& c) {
	d = 0;
	strcpy(name, c.name);
}

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

UFSet ufs;
Color color[MAX];
map<const char*, int, cmp> dict;

int main()
{
	char line[L_MAX];
	int i;
	
	while(gets(line) != NULL) {
		ufs.makeSet(); dict.clear();
		int cn = 0;
		while(strcmp(line, "*")) {
			Color c[2];
			sscanf(line, "%s %s", c[0].name, c[1].name);
			int o[2];
			for(i = 0; i < 2; i++) {
				if(dict.count(c[i].name) == 0) {
					o[i] = cn++;
					color[o[i]].clear(c[i]);
					dict[color[o[i]].name] = o[i];
				} else {
					o[i] = (dict.find(c[i].name))->second;
				}
			}
			color[o[0]].d++; color[o[1]].d++;
			ufs.unionSet(o[0], o[1]);
			gets(line);
		}
		int f = ufs.find(0);
		int euler = true;
		for(i = 1; i < cn; i++) {
			if(f != ufs.find(i)) {
				euler = false;
				break;
			}
		}
		if(euler) {
			int odd = 0;
			for(i = 0; i < cn; i++) {
				if(color[i].d % 2 == 1) {
					odd++;
					if(odd > 2) {
						break;
					}
				}
			}
			if(odd != 0 && odd != 2) {
				euler = false;
			}
		}
		if(euler) {
			printf("Possible\n");
		} else {
			printf("Impossible\n");
		}
	}
	
	return 0;
}