poj2513 Colored Sticks —— 字典树 + 并查集 + 欧拉回路

题解：通过这题了解了字典树。用字典树存储颜色，并给颜色编上序号。这题为典型的欧拉回路问题：将每种颜色当成一个点。首先通过并查集判断是否为连通图，再检验是否符合欧拉回路的特点。不过题目有一点很奇怪，在并查集中，若图为连通，不是有且仅有一个点的fa[]等于它自己吗，即类似于根节点？为什么会出现有0个的情况，这一点搞不懂。

判断欧拉路是否存在的方法：

有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。

无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

判断欧拉回路是否存在的方法：

有向图：图连通，所有的顶点出度=入度。

无向图：图连通，所有顶点都是偶数度。

一开始用C语言写，结果在传指针的时候，传的是指针的值，而不是指针的地址，所以并不能修改指针的值，故出错。

或者直接用C++的引用，简洁方便。但我还是更喜欢用C语言的传地址，因为这样更能理解其中的原理。

C语言和C++的代码都附上，区别不大。

代码如下：

C语言：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #define MAXN 500010
 5 
 6 typedef struct node
 7 {
 8     struct node *next[26];
 9     int pos;
10 }Trie, *PT;
11 
12 int n,fa[MAXN],deg[MAXN];
13 
14 int init(PT *p)
15 {
16     (*p) = (PT)malloc(sizeof(Trie));
17     (*p)->pos = 0;
18     for(int i = 0; i<26; i++)
19         (*p)->next[i] = NULL;
20 }
21 
22 int trie(char *s, int k, PT *p)
23 {
24     if(!s[k])
25     {
26         if((*p)->pos) return (*p)->pos;
27         (*p)->pos = ++n;
28         fa[n] = n;
29         return (*p)->pos;
30     }
31 
32     else
33     {
34         if(!(*p)->next[s[k]-'a'])
35             init(&((*p)->next[s[k]-'a']));
36         return trie(s,k+1,&((*p)->next[s[k]-'a']));
37     }
38 }
39 
40 int find(int a)
41 {
42     return (fa[a]==a)?a:find(fa[a]);
43 }
44 
45 void un(int x, int y)
46 {
47     x = find(x);
48     y = find(y);
49     if(x!=y)
50     fa[x] = y;
51 }
52 
53 int main()
54 {
55     char s1[15], s2[15];
56     int x,y,n1,n2;
57     PT p;
58     init(&p);
59     n1 = n2 = n = 0;
60     memset(deg,0,sizeof(deg));
61     while(scanf("%s%s",s1,s2)==2)
62     {
63         x = trie(s1,0,&p);
64         y = trie(s2,0,&p);
65         un(x,y);
66         deg[x]++; deg[y]++;
67     }
68 
69     for(int i = 1; i<=n; i++)
70     {
71         if(fa[i]==i) n1++;
72         if(deg[i]&1) n2++;
73     }
74 
75     if(n1<=1 && n2<=2)
76         puts("Possible");
77     else
78         puts("Impossible");
79     return 0;
80 }

View Code

C++：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #define MAXN 500010
 5 
 6 typedef struct node
 7 {
 8     struct node *next[26];
 9     int pos;
10 }Trie, *PT;
11 
12 int n,fa[MAXN],deg[MAXN];
13 
14 int init(PT &p)
15 {
16     p = (PT)malloc(sizeof(Trie));
17     p->pos = 0;
18     for(int i = 0; i<26; i++)
19         p->next[i] = NULL;
20 }
21 
22 int trie(char *s, int k, PT &p)
23 {
24     if(!s[k])
25     {
26         if(p->pos) return p->pos;
27         p->pos = ++n;
28         fa[n] = n;
29         return p->pos;
30     }
31 
32     else
33     {
34         if(!p->next[s[k]-'a'])
35             init(p->next[s[k]-'a']);
36         return trie(s,k+1,p->next[s[k]-'a']);
37     }
38 }
39 
40 int find(int a)
41 {
42     return (fa[a]==a)?a:find(fa[a]);
43 }
44 
45 void un(int x, int y)
46 {
47     x = find(x);
48     y = find(y);
49     if(x!=y)
50     fa[x] = y;
51 }
52 
53 int main()
54 {
55     char s1[15], s2[15];
56     int x,y,n1,n2;
57     PT p;
58     init(p);
59     n1 = n2 = n = 0;
60     memset(deg,0,sizeof(deg));
61     while(scanf("%s%s",s1,s2)==2)
62     {
63         x = trie(s1,0,p);
64         y = trie(s2,0,p);
65         un(x,y);
66         deg[x]++; deg[y]++;
67     }
68 
69     for(int i = 1; i<=n; i++)
70     {
71         if(fa[i]==i) n1++;
72         if(deg[i]&1) n2++;
73     }
74 
75     if(n1<=1 && n2<=2)
76         puts("Possible");
77     else
78         puts("Impossible");
79     return 0;
80 }

View Code