首页 > 代码库 > poj 2513 -- Colored Sticks
poj 2513 -- Colored Sticks
Colored Sticks
| Time Limit: 5000MS | Memory Limit: 128000K | |
| Total Submissions: 30037 | Accepted: 7924 |
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 redred violetcyan blueblue magentamagenta cyan
Sample Output
Possible
Hint
Huge input,scanf is recommended.
View Code
题目大意：给定一捆木棒，每根木棒的每个端点涂有某种颜色。问：是否能将这些棍子首尾相连，排成一条直线，且相邻两根棍子的连接处端点的颜色一样。
思路：首先用字典树（Trie）将每个单词编号。用并查集判断是否能连通。然后求解欧拉通路。
定理：无向图G存在欧拉通路的充要条件是：G为连通图，并且G仅有两个奇度结点或者无奇度结点。
推论1：当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点。
推论2：当G是无奇度结点的连通图时，G必有欧拉回路。
推论3：G为欧拉图的充分必要条件是G为无奇度结点的连通图。
定理：有向图D存在欧拉通路的充要条件是：D为有向图，D的基图连通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为1,另一个顶点的出度与入度之差为-1.
推论1：当D除 出入度之差为1,-1的两个顶点之外，其余顶点的出度与入度都相等时，D的有向欧拉通路必以出入度之差为1的顶点作为始点，以出入度之差为-1的顶点作为终点。
推论2：当D的所有顶点的出入度都相等时，D中存在有向欧拉回路。
推论3：有向图D为有向欧拉图的充分必要条件是D的基图为连通图，并且所有顶点的出入度都相等。
代码如下：
1 /*======================================================================
2 * Author : kevin
3 * Filename : ColoredSticks.cpp
4 * Creat time : 2014-07-31 10:13
5 * Description :
6 ========================================================================*/
7 #include <iostream>
8 #include <algorithm>
9 #include <cstdio>
10 #include <cstring>
11 #include <queue>
12 #include <cmath>
13 #define clr(a,b) memset(a,b,sizeof(a))
14 #define M 500005
15 using namespace std;
16 struct Trie{
17 Trie *next[26];
18 int num;
19 };
20 Trie *root;
21 int father[M+5],d[M+5];
22 int cnt = 1;
23 int CreateTrie(char *str)
24 {
25 Trie *p = root,*q;
26 for(int i = 0; str[i]; i++){
27 int id = str[i] - ‘a‘;
28 if(p->next[id] == NULL){
29 q = (Trie *)malloc(sizeof(Trie));
30 for(int j = 0; j < 26; j++){
31 q->next[j] = NULL;
32 q->num = 0;
33 }
34 p->next[id] = q;
35 p = p->next[id];
36 }
37 else{
38 p = p->next[id];
39 }
40 }
41 if(!(p->num))
42 p->num = cnt++;
43 return p->num;
44 }
45
46 void DelTrie(Trie *T)
47 {
48 int i;
49 if(T == NULL) return;
50 for(i = 0; i < 26; i++){
51 if(T->next[i] != NULL){
52 DelTrie(T->next[i]);
53 }
54 }
55 free(T);
56 }
57 int FindSet(int x)
58 {
59 if(x != father[x]){
60 father[x] = FindSet(father[x]);
61 }
62 return father[x];
63 }
64 void Union(int x,int y)
65 {
66 x = FindSet(x);
67 y = FindSet(y);
68 father[x] = y;
69 }
70 int main(int argc,char *argv[])
71 {
72 char str1[15],str2[15];
73 for(int i = 0; i < M; i++){
74 father[i] = i;
75 d[i] = 0;
76 }
77 root = (Trie*)malloc(sizeof(Trie));
78 for(int i = 0; i < 26; i++){
79 root->next[i] = NULL;
80 root->num = 0;
81 }
82 while(scanf("%s %s",str1,str2)!=EOF){
83 int x1 = CreateTrie(str1);
84 int x2 = CreateTrie(str2);
85 Union(x1,x2);
86 d[x1]++;
87 d[x2]++;
88 }
89 int cnt_father = 0,cnt_d = 0;
90 int t = FindSet(1);
91 for(int i = 1; i < cnt; i++){
92 int x = FindSet(i);
93 if(x == t) cnt_father++;
94 if(d[i] % 2){
95 cnt_d++;
96 }
97 }
98 if(cnt_father != cnt-1 || !(cnt_d == 0 || cnt_d == 2)){
99 printf("Impossible\n");
100 }
101 else{
102 printf("Possible\n");
103 }
104 DelTrie(root);
105 return 0;
106 }
2 * Author : kevin
3 * Filename : ColoredSticks.cpp
4 * Creat time : 2014-07-31 10:13
5 * Description :
6 ========================================================================*/
7 #include <iostream>
8 #include <algorithm>
9 #include <cstdio>
10 #include <cstring>
11 #include <queue>
12 #include <cmath>
13 #define clr(a,b) memset(a,b,sizeof(a))
14 #define M 500005
15 using namespace std;
16 struct Trie{
17 Trie *next[26];
18 int num;
19 };
20 Trie *root;
21 int father[M+5],d[M+5];
22 int cnt = 1;
23 int CreateTrie(char *str)
24 {
25 Trie *p = root,*q;
26 for(int i = 0; str[i]; i++){
27 int id = str[i] - ‘a‘;
28 if(p->next[id] == NULL){
29 q = (Trie *)malloc(sizeof(Trie));
30 for(int j = 0; j < 26; j++){
31 q->next[j] = NULL;
32 q->num = 0;
33 }
34 p->next[id] = q;
35 p = p->next[id];
36 }
37 else{
38 p = p->next[id];
39 }
40 }
41 if(!(p->num))
42 p->num = cnt++;
43 return p->num;
44 }
45
46 void DelTrie(Trie *T)
47 {
48 int i;
49 if(T == NULL) return;
50 for(i = 0; i < 26; i++){
51 if(T->next[i] != NULL){
52 DelTrie(T->next[i]);
53 }
54 }
55 free(T);
56 }
57 int FindSet(int x)
58 {
59 if(x != father[x]){
60 father[x] = FindSet(father[x]);
61 }
62 return father[x];
63 }
64 void Union(int x,int y)
65 {
66 x = FindSet(x);
67 y = FindSet(y);
68 father[x] = y;
69 }
70 int main(int argc,char *argv[])
71 {
72 char str1[15],str2[15];
73 for(int i = 0; i < M; i++){
74 father[i] = i;
75 d[i] = 0;
76 }
77 root = (Trie*)malloc(sizeof(Trie));
78 for(int i = 0; i < 26; i++){
79 root->next[i] = NULL;
80 root->num = 0;
81 }
82 while(scanf("%s %s",str1,str2)!=EOF){
83 int x1 = CreateTrie(str1);
84 int x2 = CreateTrie(str2);
85 Union(x1,x2);
86 d[x1]++;
87 d[x2]++;
88 }
89 int cnt_father = 0,cnt_d = 0;
90 int t = FindSet(1);
91 for(int i = 1; i < cnt; i++){
92 int x = FindSet(i);
93 if(x == t) cnt_father++;
94 if(d[i] % 2){
95 cnt_d++;
96 }
97 }
98 if(cnt_father != cnt-1 || !(cnt_d == 0 || cnt_d == 2)){
99 printf("Impossible\n");
100 }
101 else{
102 printf("Possible\n");
103 }
104 DelTrie(root);
105 return 0;
106 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。