poj 2513Colored Sticks

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int sign_node=26;
 7 const int max_node=550000;
 8 int f[max_node];
 9 int du[max_node];
10 int num=0;
11 int ch[max_node][sign_node];
12 int val[max_node];
13 
14 struct Trie
15 {
16     int sz;
17     void clear(){sz=1; memset(ch[0],0,sizeof(ch[0]));}
18     int idx(char c) {return c-'a';}
19 
20     int insert(char *s)
21     {
22         int u=0,n=strlen(s);
23         for(int i=0; i<n; i++){
24             int c=idx(s[i]);
25             if(!ch[u][c]){
26                memset(ch[sz],0,sizeof(ch[sz]));
27                val[sz]=0;
28                ch[u][c]=sz++;
29             }
30             u=ch[u][c];
31         }
32         if(!val[u]) val[u]=++num;
33         return val[u];
34     }
35 };
36 
37 int find(int x)
38 {
39     if(x!=f[x])
40     f[x]=find(f[x]);
41     return f[x];
42 }
43 
44 void merge(int x,int y)
45 {
46     int fx=find(x);
47     int fy=find(y);
48     if(fx!=fy){
49         f[fx]=fy;
50     }
51 }
52 
53 void inti()
54 {
55     memset(du,0,sizeof(du));
56     for(int i=0; i<=max_node; i++)
57       f[i]=i;
58 }
59 
60 int main()
61 {
62     Trie trie;
63     char a[100],b[100];
64     inti();
65     trie.clear();
66     while(scanf("%s%s",a,b)!=EOF)
67     {
68         int id1=trie.insert(a);
69         int id2=trie.insert(b);
70         du[id1]++;
71         du[id2]++;
72         merge(id1,id2);
73     }
74     int ans=0,ans1=0;
75     for(int i=1; i<=num; i++)
76     {
77         if(du[i]&1)
78         ans++;
79         if(ans>2||find(1)!=find(i))
80         {
81             printf("Impossible
");
82             return 0;
83         }
84     }
85     if(ans==1)
86     printf("Impossible
");
87     else
88     printf("Possible
");
89     return 0;
90 }
View Code