poj2513Colored Sticks(无向图判欧拉路、回路+trie树）

每个单词为一个节点并查集判联通度数为偶数或有两个为奇数 4A 第三次是由于有多余的测试输出没删掉前两次统计多少个单词统计错了

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 using namespace std;
 5 char s[500011][11];
 6 int dd,father[500011],r[500011],dk[500011];
 7 struct node
 8 {
 9     int de,da;
10     node *next[27];
11     node()
12     {
13         de = 0;
14         da = 0;
15         memset(next,0,sizeof(next));
16     }
17 };
18 int find(int x)
19 {
20     if(x!=father[x])
21     father[x] = find(father[x]);
22     return father[x];
23 }
24 void ctree(node *t,char *c,int j)
25 {
26     int i,d,k = strlen(c);
27     node *p = t;
28     for(i = 0 ; i < k ; i++)
29     {
30         d = c[i]-'a';
31         if(p->next[d]==NULL)
32         p->next[d] = new node;
33         p = p->next[d];
34     }
35     p->de++;
36     if(p->da==0)
37     {
38         dd++;
39         p->da = dd;
40     }
41     r[j] = p->da;
42     dk[p->da] = p->de;
43 }
44 int main()
45 {
46     int i = 0,j,k,n,m;
47     dd = 0;
48     node *t = new node;
49     for(j = 1; j <= 500010 ; j++)
50     father[j] = j;
51     while(scanf("%s %s",s[i],s[i+1])!=EOF)
52     {
53         /*if(s[i][0]=='#')
54         break;*/
55         ctree(t,s[i],i);
56         ctree(t,s[i+1],i+1);
57         int px = find(r[i]);
58         int py = find(r[i+1]);
59         if(px!=py)
60         father[px] = py;
61         i+=2;
62     }
63     int num = 0;
64     for(j = 1 ;j <= dd ; j++)
65     if(father[j]==j)
66     {
67         num++;
68         if(num>1)
69         break;
70     }
71     if(num>1)
72     printf("Impossible\n");
73     else
74     {
75         num = 0;
76         for(j = 1 ; j <= dd ; j++)
77         {
78             if(dk[j]%2!=0)
79             num++;
80         }
81         if(num==2||num == 0)
82         printf("Possible\n");
83         else
84         printf("Impossible\n");
85     }
86     return 0;
87 }