POJ 2513 Colored Sticks——字典树+并查集+欧拉回路

POJ 2513 Colored Sticks——字典树+并查集+欧拉回路

比较综合的一道题，套用字典树以及并查集模板。

注意：

1.字典树应该有提供单词编号的功能，这也是解题必须的要素

2.输入为空返回0，这个跟写法有关，我的写法不用特殊判断

3注意各种细节，本题综合性较强，代码量较大，稍不留神就会出现细节错误，注意及时调试

#include #include #include #include #include #define ID(x) x - 'a'using namespace std;const int maxn = 1e6;int next;struct Trie { int next[26]; int val;}tree[maxn];int add() { memset(&tree[next], 0, sizeof(Trie)); return next++;}void Insert(char *s) { int cur = 0, len = strlen(s); for (int i = 0; i < len; i++) { int id = ID(s[i]); if (!tree[cur].next[id]) { tree[cur].next[id] = add(); } cur = tree[cur].next[id]; } tree[cur].val++;}int Find(char *s) { int rt = 0, len = strlen(s); for (int i = 0; i < len; i++) { int id = ID(s[i]); if (!tree[rt].next[id]) return 0; rt = tree[rt].next[id]; } if (tree[rt].val) return rt; return 0;}int par[maxn], ran[maxn];void init() { for (int i = 0; i < maxn; i++) { par[i] = i, ran[i] = 0; }}int seek(int x) { if (par[x] == x) return x; else return par[x] = seek(par[x]);}void unite(int x, int y) { x = seek(x), y = seek(y); if (x == y) return; if (ran[x] < ran[y]) par[x] = y; else { par[y] = x; if (ran[x] == ran[y]) ran[x]++; }}int du[maxn] = {0};int main(){ next = 1; memset(&tree[0], 0, sizeof(Trie)); init(); char s1[20], s2[20]; while (scanf("%s %s", s1, s2) == 2) { Insert(s1), Insert(s2); int x = Find(s1), y = Find(s2); unite(x, y); du[x]++, du[y]++; } int temp = seek(Find(s1)); bool ok = true; for (int i = 1; i < next; i++) { int s = seek(i); if (s != i && s != temp) { ok = false; break; } } if (ok) { int cnt = 0; for (int i = 1; i < next; i++) { if (du[i] % 2) cnt++; if (cnt >= 3) break; } if (cnt >= 3 || cnt == 1) printf("Impossible\n"); else printf("Possible\n"); } else printf("Impossible\n"); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。