文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
Trie树+并查集+欧拉通路
Description
You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?
Input
Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.
Output
If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.
Sample Input
blue red
red violet
cyan blue
blue magenta
magenta cyan
Sample Output
Possible
Slyar:说下题目大意，给出n根木棍，每根木棍两端都有颜色，颜色为小于10的字符串，问能否将所有的木棍排成一排，使得每两根木棍衔接的地方颜色相同。
这题我一开始暴力做，很随意的就TLE了…看了Discuss发现要用什么”Trie”和”欧拉通路”，还要用到前几天学会的并查集…晕死，根本不知道什么是“Trie”和”欧拉通路”，遂Google了一下，得知“Trie”俗称字典树，具体内容完了发到博客上…欧拉通路完了也发博客上…本文发表2 weeks后应该可以搜索到…
对于知道以上概念者，可以看出本题就是将所有的颜色看做节点，连接两种颜色的木棍看做节点之间的连边，判断无向图中是否存在欧拉通路，判断条件是：
1、有且只有两个度为奇数的节点
2、图是连通的
由于节点是字符串，因此我们可以利用字典树将其转换成一个颜色序号。这样，统计每种颜色的出现次数就可以了。判断图是否连通，可以利用并查集：若最后所有节点在同一个集合，则图是连通的。
eg. blue (magenta magenta) (cyan cyan) (blue blue) (red red) violet
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 |
/* PKU 2513 Slyar //www.slyar.com/ */ #include <stdio.h> #include <stdlib.h> #define MAX 500001 /* father[x]表示x的父节点 */ int father[MAX]; /* rank[x]表示x的秩 */ int rank[MAX]; /* degree记录节点的度 */ int degree[MAX]; /* 记录字典树有效节点个数 */ int num = 0; /* 定义字典树节点类型 */ typedef struct node { int key; struct node *next[26]; }trie; /* 创建根节点 */ trie *root; /* 创建新节点 */ trie* New() { int i; trie *p; p = (trie*) malloc(sizeof(trie)); /* 初始化节点为未访问 */ p->key = -1; /* 初始化孩子指针 */ for (i = 0; i < 26; i++) { p->next[i] = NULL; } return p; } /* 初始化 */ void Make_Set(int x) { father[x] = x; rank[x] = 0; degree[x] = 0; } /* 查找x元素所在的集合,回溯时压缩路径 */ int Find_Set(int x) { if (x != father[x]) { father[x] = Find_Set(father[x]); } return father[x]; } /* 合并x,y所在的集合 */ void Union(int x, int y) { if (x == y) return; if (rank[x] > rank[y]) { father[y] = x; } else { if (rank[x] == rank[y]) { rank[y]++; } father[x] = y; } } /* 向以root为根的树中插入字符串s */ int Insert(trie *root, char *s) { int i; trie *p = root; for (i = 0; s[i] != '\0'; i++) { /* 节点若不存在则创建 */ if (p->next[s[i] - 'a'] == NULL) { p->next[s[i] - 'a'] = New(); } /* 向下一层移动 */ p = p->next[s[i] - 'a']; } /* 得到并返回颜色节点序号 */ if (p->key == -1) { p->key = ++num; } return p->key; } /* 主函数 */ int main() { int i, x, y, sum; char s1[11], s2[11]; /* 初始化集合 */ for (i = 0; i < MAX; i++) { Make_Set(i); } /* 初始化根节点 */ root = New(); /* 处理字符串 */ while(scanf("%s%s", s1, s2) != EOF) { /* 插入颜色，得到颜色节点序号 */ x = Insert(root, s1); y = Insert(root, s2); /* 更新颜色节点的度 */ degree[x]++; degree[y]++; /* 合并两根木棍 */ Union(Find_Set(x), Find_Set(y)); } sum = 0; /* 求度为奇数的点的个数 */ for (i = 1; i < num; i++) { if(degree[i] % 2) sum++; } /* 若度大于2则肯定不可能 */ if (sum > 2) { printf("Impossible\n"); } /* 否则考察图是否连通 */ else { /* 考察所有的点是否在一个集合 */ for (i = 2; i < num; i++) { if (Find_Set(i) != Find_Set(1)) { printf("Impossible\n"); return 0; } } printf("Possible\n"); } //system("pause"); return 0; } |
