1
//Source Code
2
3//Problem: 2513 User: SkyOrNight
4//Memory: 73304K Time: 1172MS
5//Language: C++ Result: Accepted
6
7//Source Code
8#include<stdio.h>
9#include<string.h>
10const int CHARN=26;//trie树的字符数
11const int MCN=500020;//颜色最多种类
12
struct TrieNode
{//trie树的结构体
13
int key;
14 struct TrieNode* child[CHARN];
15
struct TrieNode(){
16 int i;
17 key=-1;
18 for(i=0;i<CHARN;i++)
19 child[i]=NULL;
20
}
21
};
22struct TrieNode* trieRoot;
23int degree[MCN];//以颜色为顶点的度
24int set[MCN];//并查集使用的数组初始时set[x]=x，表示元素x在集合x中
25int Index(char c);// 返回c的在字典中的序号a-0，b-1;
26int cnt;//给颜色编号的序号，从cnt=0开始编号,最后cnt为颜色种类的数目
27int Insert(struct TrieNode*root,char *word);//在trie树中插入一种颜色，并返回此颜色的序号
28void UnionSet(int bn,int en);//对颜色bn,en的stick进行处理
29int Find(int x);//找到元素x在并查集中所在的集合，并压缩路径
30void InitSet();//初始化并查集，即使set[x]=x;
31int main(void){
32 char b[11],e[11];//stick的两头的颜色
33 int bn,en;
34 cnt=0;
35 trieRoot=new TrieNode();
36 InitSet();
37 memset(degree,0,sizeof(degree));
38 while(scanf("%s%s",b,e)!=EOF){
39 bn=Insert(trieRoot,b);
40 en=Insert(trieRoot,e);
41 degree[bn]++; degree[en]++;
42 UnionSet(bn,en);
43 }
44 int i,c1t=0;
45 bool possible=true;
46 for(i=0;i<cnt;i++){
47 if(degree[i]%2!=0){
48 c1t++;
49 if(c1t>2){
50 possible=false;
51 break;
52 }
53 }
54 }
55 if(possible==true){
56 int n=Find(0);
57 for(i=1;i<cnt;i++){
58 if(n!=Find(i)){
59 possible=false;
60 break;
61 }
62 }
63 if(possible==true)
64 printf("Possible\n");
65 else
66 printf("Impossible\n");
67 }
68 else
69 printf("Impossible\n");
70 return 0;
71}
72int Index(char c){
73 return c-'a';
74}
75int Insert(struct TrieNode*root,char*word){
76 while(*word!='\0'){
77 int ind=Index(*word);
78 if(root->child[ind]==NULL)
79 root->child[ind]=new TrieNode();
80 root=root->child[ind];
81 word++;
82 }
83 if(root->key==-1){
84 root->key=cnt; cnt++;
85 }
86 return root->key;
87}
88void UnionSet(int bn,int en){
89 if(bn==en)return;
90 int x=Find(bn);
91 int y=Find(en);
92 set[x]=y;
93}
94void InitSet(){
95 int i;
96 for(i=0;i<MCN;i++){
97 set[i]=i;
98 }
99}
100int Find(int x){
101 int b=x;
102 while(set[x]!=x){
103 x=set[x];
104 }
105 while(b!=set[b])//压缩路径
106 {
107 b=set[b];
108 set[b]=x;
109 }
110 return x;
111}
112
posted on 2011-04-25 14:45
SkyOrNight 阅读(189)
评论(0) 编辑 收藏 引用 所属分类:
ACM