pku 2513 Colored Sticks 欧拉通路问题

迷南。 2022-07-10 23:57 101阅读 0赞

这题的本质是欧拉通路的思想.

不过还需要并查集来判断是否是联通图, 用trie存储所有的字符串.

\#include <iostream> using namespace std; \#define swap(i,j) \{int temp=i; i = j; j = temp;\} struct Node \{ int index; Node\* arr\[26\]; Node() \{ index = -1; memset(arr, 0, sizeof(arr)); \} \}; int parent\[500001\]; int degree\[500001\]; Node\* root = new Node(); //根节点 int words\_count = 0; //不同的单词的总的个数 int get\_num(char\* str) \{ Node\* p = root; while(\*str) \{ int index = \*str-'a'; if(!p->arr\[index\]) p->arr\[index\] = new Node(); p = p->arr\[index\]; str++; \} if(p->index == -1) p->index = words\_count++; return p->index; \} int ufset\_find(int i) \{ int p = i; while(parent\[p\] >= 0) p = parent\[p\]; while(i != p) \{ parent\[i\] = p; i = parent\[i\]; \} return p; \} void ufset\_union(int i, int j) \{ i = ufset\_find(i); j = ufset\_find(j); if(i == j) return; if(parent\[i\] < parent\[j\]) swap(i, j); parent\[i\] += parent\[j\]; //注意这两行的先后顺序! parent\[j\] = i; \} int main() \{ memset(parent, -1, sizeof(parent)); memset(degree, 0, sizeof(degree)); char str1\[11\], str2\[11\]; while(scanf("%s %s", str1, str2) != EOF) \{ int i = get\_num(str1); int j = get\_num(str2); degree\[i\]++; degree\[j\]++; ufset\_union(i, j); \} if(!words\_count) \{ printf("Possible/n"); return 0; \} if(parent\[ufset\_find(0)\] + words\_count) \{ printf("Impossible/n"); return 0; \} int cnt = 0; for(int i = 0; i < words\_count; ++i) if(degree\[i\]&1) cnt++; if(cnt == 2 || cnt == 0) printf("Possible/n"); else printf("Impossible/n"); return 0; \}