首页 > 代码库 > 【POJ】2513 Colored Sticks
【POJ】2513 Colored Sticks
字典树+并查集。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 5 #define MAXN 500005 6 #define MAXL 11 7 #define TRIEN 26 8 9 typedef struct Trie { 10 int v; 11 Trie *next[TRIEN]; 12 Trie() { 13 v = 0; 14 for (int i=0; i<TRIEN; ++i) 15 next[i] = NULL; 16 } 17 } Trie; 18 19 Trie root; 20 int pre[MAXN], deg[MAXN], n = 1; 21 22 void create(char str[], int in) { 23 int i = 0, id; 24 Trie *p = &root, *q; 25 26 while (str[i]) { 27 id = str[i] - ‘a‘; 28 ++i; 29 if (p->next[id] == NULL) { 30 q = new Trie(); 31 p->next[id] = q; 32 } 33 p = p->next[id]; 34 } 35 p->v = in; 36 } 37 38 int Tfind(char str[]) { 39 int i = 0, id; 40 Trie *p = &root; 41 42 while (str[i]) { 43 id = str[i] - ‘a‘; 44 ++i; 45 if (p->next[id] == NULL) 46 return 0; 47 p = p->next[id]; 48 } 49 50 return p->v; 51 } 52 53 int find(int x) { 54 return x==pre[x] ? x:pre[x]=find(pre[x]); 55 } 56 57 void merge(int a, int b) { 58 a = find(a); 59 b = find(b); 60 if (a != b) 61 pre[b] = a; 62 } 63 64 bool judge() { 65 int cnt = 0, i; 66 if (n == 1) 67 return true; 68 for (i=1; i<n; ++i) { 69 if (pre[i] == i) 70 ++cnt; 71 if (cnt > 1) 72 return false; 73 } 74 if (!cnt) 75 return false; 76 cnt = 0; 77 for (i=1; i<n; ++i) 78 if (deg[i] & 1) 79 ++cnt; 80 if (cnt==0 || cnt==2) 81 return true; 82 else 83 return false; 84 } 85 86 int main() { 87 char a[MAXL], b[MAXL]; 88 int i, k; 89 90 memset(deg, 0, sizeof(deg)); 91 for (i=0; i<MAXN; ++i) 92 pre[i] = i; 93 94 while (scanf("%s %s", a, b) != EOF) { 95 k = Tfind(a); 96 if (k) 97 deg[k]++; 98 else { 99 create(a, n);100 k = n;101 deg[n++] = 1;102 }103 i = Tfind(b);104 if (i)105 deg[i]++;106 else {107 create(b, n);108 i = n;109 deg[n++] = 1;110 }111 merge(k, i);112 }113 114 if (judge())115 printf("Possible\n");116 else117 printf("Impossible\n");118 119 return 0;120 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。