题目链接：?id=2513题目大意：给一些木棍，两端都有颜色，只有两根对应的端点颜色相同才能相接，问能不能把它们接成一根木棍题目分析：题意不难，，典型的无向图判断是否存在欧拉通路或回路的问题，但是字符串太多，用map超时，这里使用Trie树给每个木棍标号，判断是否存在欧拉通路或回路抓住两点就行了，第一是图连通，第二是奇数度结点只能有0个(回路)或2个(通路)#include <cstdio>#include <cstring>int const MAX = 500005;int fa[MAX], d[MAX], cnt;struct Trie{int sz, t[MAX][15];int jud[MAX];Trie(){sz = 1;memset(t[0], -1, sizeof(t));jud[0] = 0;}void clear(){sz = 1;memset(t[0], -1, sizeof(t));jud[0] = 0;}int idx(char c){return c – 'a';}void insert(char* s, int v){int u = 0, len = strlen(s);for(int i = 0; i < len; i++){int c = idx(s[i]);if(t[u][c] == -1){memset(t[sz], -1, sizeof(t[sz]));jud[sz] = 0;t[u][c] = sz++;}u = t[u][c];}jud[u] = v;}int search(char* s){int u = 0, len = strlen(s);for(int i = 0; i < len; i++){int c = idx(s[i]);if(t[u][c] == -1)return -1;u = t[u][c];}if(jud[u])return jud[u];return -1;}}t;void Init(){for(int i = 0; i < MAX; i++)fa[i] = i;}int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}void Union(int a, int b){int r1 = Find(a);int r2 = Find(b);if(r1 != r2)fa[r1] = r2;}bool eluer(){int sum = 0, t = -1;for(int i = 1; i < cnt; i++)if(d[i] % 2)sum++;if(sum != 0 && sum != 2)return false;for(int i = 1; i < cnt; i++){if(t == -1)t = Find(i);else if(Find(i) != Find(t))return false;}return true;}int main(){char s1[20],s2[20];cnt = 1;Init();t.clear();while(scanf("%s %s", s1, s2) != EOF){if(t.search(s1) == -1)t.insert(s1, cnt++);int u = t.search(s1);if(t.search(s2) == -1)t.insert(s2, cnt++);int v = t.search(s2);Union(u, v);d[u]++;d[v]++;}if(eluer())printf("Possible\n");elseprintf("Impossible\n");}
一只小狗在沙漠中旅行，找到了电线杆，结果还是憋死了，
