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 500001struct 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;intnew_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){intpx, 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(){charcolor1[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 Answerif (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;}