poj 2513 trie + 并查集 + 欧拉通路

 

#include <stdio.h>
#include <string.h>

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define M 530001
#define N 500001

struct trie_node {
	int color_id; 			/* 叶子节点存储颜色编号，从1开始 */
	int child[26];			/* 分支节点，静态链表表示 */
};
struct trie_node trie_tree[M];	/* trie树的静态链表表示法，trie_tree[0]是树根 */
int  current;					/* Trie树当前使用了多少个节点 */

int	 parent[N];					/* 并查集树形表示，parent[u] = r，若r > 0，u的
								   父亲为r, 若r < 0, 则u是根节点，其高度为-r */
int  degree[N];
int  n;							/*顶点个数, 即有多少种颜色 */

/* 把单词插入Trie树，如果单词已存在直接返回颜色编号，
 * 不存在则插入，同时返回新生成的颜色编号 
 */
int insert(char *color)
{
	char				*p;
	struct trie_node 	*node;
	int					new_node;

	node = trie_tree;
	//沿着树根一直往下插
	for (p = color; *p != '\0'; p++) {
		debug("开始插入 %c...\n", *p);
		if (node->child[*p-'a'] == 0) {
			debug("没有%c, 新建节点\n", *p);
			node->child[*p-'a'] = current++;
		}
		else {
			debug("存在%c\n", *p);
		}
		node = trie_tree + node->child[*p-'a'];
	}
	//到达记录统计单词次数的节点
	if (node->color_id == 0) {
		node->color_id = ++n;
	} 
	debug("%s插入完成，其编号为%d\n", color, node->color_id);
	return node->color_id;
}

/* 找i的根节点 */
int find(int i)
{
	for(; parent[i] > 0; i = parent[i]) ;
	return i;
}

void merge(int x,int y)
{
	int		px, py;

	px = find(x);
	py = find(y);
	if (px == py) return;
	debug("%d的树根为%d，树高=%d，%d的树根为%d, 树高=%d\n", x, px, -parent[px], y, py, -parent[py]);
	if (parent[px] < parent[py]) {	/* x所在的树比y所在的树要高 */
		parent[py] = px;
		debug("合并后树根为%d, 高度=%d\n", px, -parent[px]);
	}
	else if (parent[px] > parent[py]) { /* x所在的树比y所在的树要矮 */
		parent[px] = py;
		debug("合并后树根为%d, 高度=%d\n", py, -parent[py]);
	}
	else {
		parent[py] = px;
		parent[px]--;	/* 树的高度加1 */
		debug("合并后树根为%d, 高度=%d\n", px, -parent[px]);
	}
}

int main()
{
	char	color1[11], color2[11];
	int 	u, v, subgraph, count;

	current = 1;
	n = 0;
	memset(parent, -1, sizeof(parent));
	memset(degree, 0, sizeof(degree));

	while (scanf("%s %s", color1, color2) != EOF) {
		u = insert(color1);
		v = insert(color2);
		degree[u]++;
		degree[v]++;
		merge(u, v);
	}

	//空数据打印Possible, 否则Wrong Answer
	if (n == 0) {
		printf("Possible\n");
		return 0;
	}

	//计算奇数度顶点的个数
	count = 0;
	for (u = 1; u <= n; u++) {
		if (degree[u]%2 != 0) {
			if(++count > 2) break;
		}
	}
	debug("奇数度的顶点个数为%d\n", count);

	/* 计算并查集有几个分支，只有一个分支，说明图是连通的, 
	 * 如果有两个或两个以上的分支，则图不是连通的
	 */
	subgraph = 0;
	if (count == 0 || count == 2) {
		for (u = 1; u <= n; u++) {
			/* parent[u] < 0说明u是树根，有多少树根，并查集就有多少个分支 */
			if (parent[u] < 0) { 
				if (++subgraph > 1) {
					break;
				}
			}
		}
		if (subgraph == 1) {
			printf("Possible\n");
			return 0;
		}
	}
	printf("Impossible\n");
	return 0;
}