Colored Sticks (字典树哈希+并查集+欧拉路)

Time Limit: 5000MS		Memory Limit: 128000K
Total Submissions: 27704		Accepted: 7336

Description

You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?

Input

Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.

Output

If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.

Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan

Sample Output

Possible

Hint

Huge input,scanf is recommended.

题意：给定若干个棒，棒的两端涂上不同的颜色，问是否能将棒首尾相连且不同棒相接的一端颜色相同；

思路：题意容易理解，但开始完全没思路，经大神指点后，可以用欧拉路的思想；可以把涂颜色的棒的两端看成结点，

把木棒看成边，相同颜色的就是一个结点，要将木棒连成一个直线，也就是“一笔画”问题；

无向图存在欧拉路的充要条件是：

>图是连通的（可以用并查集判断，开始将每个点初始化一棵树，经过输入将有相同祖先的结点合并到一个集合中，

最后任意枚举一个节点，若他们有共同的祖先，说明图是连通的）；

>度数为奇数的结点有0个或两个；

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 int degree[500010],set[500010],id = 1;
 5 
 6 struct node
 7 {
 8     int flag;
 9     int id;
10     struct node* next[26];
11 };
12 struct node* root;
13 
14 //开辟新结点
15 struct node* creat()
16 {
17     struct node *p = (struct node*)malloc(sizeof(struct node));
18     p->flag = 0;
19     for(int i = 0; i < 26; i++)
20         p->next[i] = NULL;
21     return p;
22 }
23 
24 int find(int x)
25 {
26     if(set[x] != x)
27         set[x] = find(set[x]);//路径压缩；
28     return set[x];
29 }
30 
31 //字典树哈希
32 int Hash(char s[])
33 {
34     struct node *p = root;
35     for(int i = 0; s[i]; i++)
36     {
37         if(p->next[s[i]-'a'] == NULL)
38             p->next[s[i]-'a'] = creat();
39         p = p->next[s[i]-'a'];
40     }
41     if(p->flag != 1)
42     {
43         p->flag = 1;
44         p->id = id++;
45     }
46     return p->id;
47 }
48 
49 int check()
50 {
51     int sum = 0;
52     int x = find(1);
53     for(int i = 2; i < id; i++)
54         if(find(i) != x)//没有共同祖先，图是不连通的，直接返回；
55             return 0;
56     for(int i = 1; i < id; i++)
57     {
58         if(degree[i]%2)
59             sum++;
60     }
61     if(sum == 0 || sum == 2)
62         return 1;//图是连通的并且奇度数是0或2，说明有欧拉路；
63     return 0;//图是连通的但奇度数不是0或2也不存在欧拉路；
64 }
65 
66 int main()
67 {
68     memset(degree,0,sizeof(degree));
69     for(int i = 1; i <= 500000; i++)
70         set[i] = i;//所有节点初始化为一棵树
71     char s1[12],s2[12];
72     int u,v;
73     root = creat();
74     while(scanf("%s %s",s1,s2) != EOF)
75     {
76         u = Hash(s1);
77         v = Hash(s2);
78         degree[u]++;
79         degree[v]++;
80         int x = find(u);
81         int y = find(v);
82         if(x != y)
83             set[x] = y;
84     }
85     if(check()) printf("Possible
");
86     else printf("Impossible
");
87     return 0;
88 }

View Code