POJ_2513Colored Sticks 字典树+

比较考察技术含量的一道题。

参考链接:http://blog.csdn.net/lyy289065406/article/details/6647445

题目链接:http://poj.org/problem?id=2513

首先差不多能想到这事欧拉路，然后发现没法构图。没有尝试使用map，刚好最近在学字典树就直接上了。

然后就是并查集判断图连通。

参考链接里面的：连通图判断（并查集）+字典树（映射字符串）+欧拉路（奇数节点0个或2个）

注意：最后需要销毁字典树所创建的节点，不然会RE！

代码：先字典树，然后并查集，然后直接主函数中判断欧拉路

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <cstring>
  6 #include <string>
  7 using namespace std;
  8 #define maxm 500055
  9 #define maxn 500055
 10 #define maxnode 30
 11 
 12 struct trie {
 13     trie * next[maxnode];
 14     int id;
 15 };
 16 trie *root;
 17 int totid = 1;
 18 trie * newnode() {
 19     trie * t;
 20     t = (trie*)malloc(sizeof(trie));
 21     t->id = 0;
 22     for (int i = 0; i < maxnode; i++)
 23         t->next[i] = 0;
 24     return t;
 25 }
 26 void init() {
 27     root = (trie *)malloc(sizeof(trie));
 28     root->id = 0;
 29     for (int i = 0; i < maxnode; i++)
 30         root->next[i] = 0;
 31 }
 32 int insert_find_Str(char s[]) {
 33     trie *p = root, *q;
 34     int len = strlen(s), i = 0;
 35     while (i < len && p->next[s[i] - 'a']) {
 36         p = p->next[s[i] - 'a'];
 37         i++;
 38     }
 39     if (i == len && p->id) return p->id;
 40     else if (i == len) return p->id = totid++;
 41     while (i < len) {
 42         q = newnode();
 43         p->next[s[i] - 'a'] = q;
 44         p = p->next[s[i] - 'a'];
 45         i++;
 46     }
 47     p->id = totid++;
 48     return p->id;
 49 }
 50 void deltrie(trie* node) {
 51     while (node) {
 52         for (int i = 0; i < 26; i++) {
 53             if ((node->next)[i])
 54                 deltrie((node->next)[i]);
 55         }
 56         free(node);
 57         node = 0;
 58     }
 59 }
 60 
 61 int f[maxn];
 62 int deg[maxn];
 63 char st[maxn], anost[maxn];
 64 
 65 void init_ds(int n) {
 66     for (int i = 1; i < n - 1; i++)
 67         f[i] = i;
 68 }
 69 int find(int x) {
 70     if (x == f[x])
 71         return f[x];
 72     return f[x] = find(f[x]);
 73 }
 74 void unite(int x, int y) {
 75     int fx = find(x);
 76     int fy = find(y);
 77     if (fx == fy) return;
 78     f[fx] = fy;
 79 }
 80 
 81 int main() {
 82     init();
 83     init_ds(maxn);
 84     memset(deg, 0, sizeof deg);
 85     while (scanf("%s", st) > 0) {
 86         scanf("%s", anost);
 87         int a = insert_find_Str(st);
 88         int b = insert_find_Str(anost);
 89         deg[a]++; deg[b]++;
 90         unite(a, b);
 91     }
 92     if (totid == 1) {
 93         printf("Possible
");
 94         return 0;
 95     }
 96     bool flag = true;
 97     for (int i = 2; i < totid; i++) {
 98         if (find(i) != find(i - 1)) {
 99             flag = false;
100             break;
101         }
102     }
103     if (!flag) {
104         printf("Impossible
");
105     }
106     else {
107         int oddnum = 0;
108         for (int i = 1; i < totid; i++)
109             if (deg[i] & 1) oddnum++;
110         if (oddnum == 0 || oddnum == 2) {
111             printf("Possible
");
112         }
113         else
114             printf("Impossible
");
115     }
116     deltrie(root);
117 }

题目：

Colored Sticks

Time Limit: 5000MS		Memory Limit: 128000K
Total Submissions: 37263		Accepted: 9775

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

Hint

Huge input,scanf is recommended.