首页 > 代码库 > POJ 2513 - Colored Sticks
POJ 2513 - Colored Sticks
题解:http://blog.csdn.net/lyy289065406/article/details/6647445
正如题解所说,是一道综合好题,讲真,如果不看题解,绝对不会想到同事用并查集和trietree……
题解里什么都好,就是有个地方有点坑,不要用cin,乖乖用scanf,不要以为题解用了cin就能过了
1 #include<cstdio> 2 #include<iostream> 3 #include<map> 4 #include<cstring> 5 #define MAX 250000*2+5 6 using namespace std; 7 8 int color_size; 9 struct trienode 10 { 11 bool flag; 12 int num; 13 trienode *next[26]; 14 }root; 15 trienode *newnode() 16 { 17 trienode *p=new trienode; 18 p->flag=0; 19 p->num=0; 20 for(int i=0;i<26;i++) p->next[i]=0; 21 return p; 22 } 23 int hash(char s[]) 24 { 25 int i,k; 26 int len = strlen(s); 27 trienode *p=&root; 28 for (i=0;i<len;i++) 29 { 30 k=s[i]-‘a‘; 31 if(p->next[k] == 0) p->next[k] = newnode(); 32 p = p->next[k]; 33 } 34 if(p->flag) return p->num; 35 else 36 { 37 p->num=(++color_size); 38 p->flag=1; 39 return p->num; 40 } 41 } 42 43 int par[MAX],rank[MAX]; 44 void UFS_init() 45 { 46 for(int i=1;i<=MAX;i++) par[i]=i,rank[i]=0; 47 } 48 int find(int x){ 49 return (par[x]==x?x:par[x]=find(par[x])) ; 50 } 51 void unite(int x,int y) 52 { 53 x=find(x),y=find(y); 54 if(x == y) return; 55 if(rank[x] < rank[y]) par[x]=y; 56 else 57 { 58 par[y]=x; 59 if(rank[x] == rank[y]) rank[x]++; 60 } 61 } 62 int degree[MAX]; 63 int main() 64 { 65 char s1[11],s2[11]; 66 color_size=0; 67 memset(degree,0,sizeof(degree)); 68 UFS_init(); 69 while(scanf("%s %s",s1,s2)!=EOF) 70 { 71 int s1_num=hash(s1); 72 int s2_num=hash(s2); 73 degree[s1_num]++; 74 degree[s2_num]++; 75 if(find(s1_num)!=find(s2_num)) unite(s1_num,s2_num); 76 } 77 int cnt=0; 78 int s=find(1); 79 for(int i=1;i<=color_size;i++) 80 { 81 if(degree[i]%2) cnt++; 82 if(cnt>=3){ 83 printf("Impossible\n"); 84 return 0; 85 } 86 if(find(i)!=s){ 87 printf("Impossible\n"); 88 return 0; 89 } 90 } 91 if(cnt==1){ 92 printf("Impossible\n"); 93 return 0; 94 } 95 else{ 96 printf("Possible\n"); 97 return 0; 98 } 99 }
POJ 2513 - Colored Sticks
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。