瑞瑞的木棍：Hash函数题目大意：有N根两端被染色的木棍，只有两个颜色相同的端点才能连接在一起，求是否能将木棍连成一条直线。需要解决：如何处理用单词表示的颜色如何判断是否能连成一条直线单词的处理：在计算过程中用单词表示颜色显然是很不方便的，所以常用的做法就是将单词编号。使用hash表将每个单词对应唯一的hash值对新出现的hash值编号，使每个单词分别对应编号1...M判断木棍是否能连成一条线：将每种颜色看作一个点，将每根木棍看作一条边，则问题转化为判断该图是否存在欧拉路径。存在欧拉路径的条件：图是连通的每个点都与偶数条边相连或有且只有2个点与奇数条边相连解题思路：1.用hash表将单词编号，将木棍以边的形式储存2.统计与奇数条边相连的点的数量3.判断图是否连通：方法1：用dfs或bfs判断一个点是否能到达其他所有点方法2：用并查集判断所有点是否属于同一个集合参考程序：/*H:ColoredSticks*/#include<stdio.h>#include<stdlib.h>typedefstruct{charc1[11];charc2[11];}Stick;typedefstruct{char*col;}Color;Sticksticks[250020];intssize=0;Colorcolors[500020];Colorcolorindex[500020];intsetsize=0;intcolorset[500020];intcsize=0;intGetRoot(intx){if(colorset[x]<0)returnx;elsereturnGetRoot(colorset[x]);}voidUnion(inta,intb){introotA=GetRoot(a);introotB=GetRoot(b);if(rootA==rootB)return;if(colorset[rootA]<=colorset[rootB]){colorset[rootA]+=colorset[rootB];colorset[rootB]=rootA;if(colorset[rootA]==-1*setsize){printf("Possible\n");exit(0);}}else{colorset[rootB]+=colorset[rootA];colorset[rootA]=rootB;if(colorset[rootB]==-1*setsize){printf("Possible\n");exit(0);}}}intcmp_sticks(Stick*a,Stick*b){intresult=0;result=strcmp(a->c1,b->c1);if(result==0)result=strcmp(a->c2,b->c2);returnresult;}intcmp_colors(Color*a,Color*b){returnstrcmp(a->col,b->col);}intbinsearch(char*key,intmin,intmax){intcmp;intmiddle=(min+max)/2;if(min==max)returnmin;cmp=strcmp(key,colorindex[middle].col);if(cmp<0){returnbinsearch(key,min,middle-1);}elseif(cmp>0){returnbinsearch(key,middle+1,max);}else{returnmiddle;}}intmain(){chart1[11];chart2[11];char*current;inti,index1,index2;intoddcount,curcount;freopen("stick.in","r",stdin);freopen("stick.out","w",stdout);while(scanf("%s%s",t1,t2)==2){if(strcmp(t1,t2)<0){strcpy(sticks[ssize].c1,t1);strcpy(sticks[ssize++].c2,t2);}else{strcpy(sticks[ssize].c2,t1);strcpy(sticks[ssize++].c1,t2);}}if(ssize==0){printf("Possible\n");return0;}qsort(sti