题目链接：http://poj.org/problem?id=2513 题意：由若干根木棍，每根木棍的两头都有不同的颜色，只有颜色相同，两根木棍才能连在一起，问你能否把所有木棍都连在一起 解析：其实就是判断无向图中是否有欧拉道路，由于木棍可能有3e5那么大，所以用map来转换是会超时的，更好的办法是采用字典树，本题还有一个坑点就是有可能一根木棍都没有
#include <iostream> #include <algorithm> #include <string> #include <cstring> #include <cstdio> using namespace std; const int maxn = 3e5+100; struct Trie { int isEnd; Trie *next[26]; int id; }; int fa[maxn],cnt; int du[maxn]; void init() { memset(du,0,sizeof(du)); for(int i=0;i<maxn;i++) fa[i] = i; } int findFa(int x) { if(x==fa[x]) return x; return fa[x] = findFa(fa[x]); } void merge(int u,int v) { int t1 = findFa(u); int t2 = findFa(v); if(t1!=t2) fa[t1] = t2; } int getId(Trie *root,char *s) { Trie *p = root; int i = 0; while(s[i]!=0) { if(p->next[s[i]-'a']==NULL) { Trie *tmp = new Trie; for(int j=0;j<26;j++) tmp->next[j] = NULL; tmp->isEnd = 0; tmp->id = 0; p->next[s[i]-'a'] = tmp; } p = p->next[s[i]-'a']; i++; } if(p->isEnd) return p->id; else { p->isEnd = 1; p->id = cnt++; return p->id; } } int main(void) { char a[20],b[20]; cnt = 0; init(); Trie *root = new Trie; for(int i=0;i<26;i++) root->next[i] = NULL; root->id = 0; while(~scanf("%s %s",a,b)) { int t1 = getId(root,a); int t2 = getId(root,b); merge(t1,t2); du[t1]++; du[t2]++; } int t1 = 0,t2 = 0; for(int i=0;i<cnt;i++) { if(fa[i]==i) t1++; if(du[i]%2) t2++; } if((t1==0||t1==1)&&(t2==0 || t2==2)) puts("Possible"); else puts("Impossible"); return 0; }