【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
");
116     else
117         printf("Impossible
");
118 
119     return 0;
120 }