题源：https://vjudge.net/problem/11158/origin 题意：给你一堆木棒，木棒两端各有一种颜色，问你木棒能否相同颜色首尾相接。 思路：木棒相当于图中的边，而两端的颜色是图中的点，但是颜色是用字符串表示的，所以这里需要用map或者其他东西把字符串和数字来对应一下子。 这里我们用字典树，给单词结尾（即单词）计数。 最后每一个字符串（颜色）对应到了一个数字，就是简单的半欧拉图的判定了： 半欧拉图就是：1、图是联通的。2、所有点的度数为偶数或者有两个点的度数为奇数。 那么并查集就是用来判断图是否联通。就没了。 下面是AC代码 2e6 MLE了 1e6 AC了
/* 每行两个单词 两个是奇数 字典树做法 欧拉回路 不！ 是半欧拉图 不必是回路 要求：所有的棒子能连成一条直线就好 */ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<stack> #include<string> #include<map> #include<set> #include<algorithm> #define ll long long #define inf 0x3f3f3f3f #define MID (t[k].l+t[k].r)>>1 #define cl(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn=1e6+10; int cnt_node,cnt_word;//统计有多少个不同的结点和单词 int t[maxn][26]; //book记录该结点代表的单词是否出现过 并统计次数 //pre是并查集 deg是统计度数 int book[maxn],pre[maxn],deg[maxn]; int _insert(char *s){ //将目前的单词插入字典树 并获得该单词编号（cnt int root=0; int len=strlen(s); for(int i=0;i<len;i++){ int id=s[i]-'a'; //注意这里后面不能是cnt_node++ 因为这样第一个还是没有的！！！ //就这里 一失足成千古恨呐！！！ if(!t[root][id]) t[root][id]=++cnt_node; //———————————注意这里↑一定是++cnt_node root=t[root][id]; } if(!book[root]){//单词计数从1开始吧 因为还肩负着不能是0 cnt_word++; book[root]=cnt_word; pre[cnt_word]=cnt_word;//这里不必再判断pre[0]=0 因为看book就行 } return book[root]; } //并查集部分 int find(int x){ if(x==pre[x]) return x; return pre[x]=find(pre[x]); } void join(int a,int b){ int fa=find(a),fb=find(b); if(fa<fb) pre[fb]=fa; else pre[fa]=fb; } void init(){ cnt_node=0,cnt_word=0; cl(t,0); cl(book,0); cl(pre,0); cl(deg,0); } int main(){ //freopen("in.txt","r",stdin); init(); char s1[15],s2[15]; while(scanf("%s%s",s1,s2)!=EOF){ int a=_insert(s1); int b=_insert(s2); deg[a]++,deg[b]++; if(find(a)!=find(b)){ join(a,b); } } int temp=find(1);//所有祖先理论上应该等于这个 int cnt_odd=0;//度数为奇数的数量 for(int i=1;i<=cnt_word;i++){ //printf("%d %d\n",deg[i],find(i)); if(deg[i]&1) cnt_odd++; if(cnt_odd==3) break;//不行 if(find(i)!=temp){ printf("Impossible\n"); return 0; } } if(cnt_odd==0||cnt_odd==2) printf("Possible\n"); else printf("Impossible\n"); return 0; }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.
