彩色棒
时间限制：1000 ms | 内存限制：128000 KB
难度：5
- 描述
- 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?
- 输入
- the frist line have a number k(0<k<=10),that is the number of case. each case contais a number m,then have m line, 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 13 characters. There is no more than 250000 sticks.
- 输出
- If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.
- 样例输入
-
1 5 blue red red violet cyan blue blue magenta magenta cyan
- 样例输出
-
Possible
#include<stdio.h> #include<string.h> #include<malloc.h> struct node { int order; struct node *next[26]; }; int t;//记录颜色种类 int father[250001];//记录并查集父亲节点 int degree[250001];//记录每种颜色出现的次数 int insert(char *str,node *T)//插入构建字典树 { int len,id,flat=0,i,j; node *p,*q; len=strlen(str); p=T; for(i=0;i<len;++i) { id=str[i]-'a'; if(p->next[id]==NULL) { flat=1; q=(node *)malloc(sizeof(node)); for(j=0;j<26;++j) q->next[j]=NULL; p->next[id]=q; } p=p->next[id]; } if(flat)//字典树向前延伸，出现新的颜色 { p->order=t;//在此记录此种颜色的 序号 degree[t++]++;//增加出现次数 return p->order; } else { if(p->order==0)//可能有这种情况 abdse abd虽然没有延伸，但也是新颜色 { p->order=t; degree[t++]++; return p->order; } degree[p->order]++; return p->order; } } int findfather(int i) { if(father[i]==-1) return i; else return findfather(father[i]); } void merge(int a,int b)//合并 { a=findfather(a); b=findfather(b); if(a!=b) { if(father[a]<father[b]) father[b]=a; else father[a]=b; } } int main() { char str1[14],str2[14]; int flag,i,num1,num2,n,x; node *T; scanf("%d",&x); while(x--) { T=(node *)malloc(sizeof(node)); T->order=0; memset(degree,0,sizeof(degree)); memset(father,-1,sizeof(father)); for(i=0;i<26;++i) T->next[i]=NULL; t=1; scanf("%d",&n); if(n==0) { printf("Possible\n"); continue; } while(n--) { scanf("%s%s",str1,str2); num1=insert(str1,T); num2=insert(str2,T); merge(num1,num2); } flag=0; for(i=1;i<t;++i) if(father[i]==-1)//统计根节点 ++flag; if(flag>1) printf("Impossible\n"); else { flag=0; for(i=1;i<t;++i) if(degree[i]&1) flag++; if(flag==2||flag==0) printf("Possible\n"); else printf("Impossible\n"); } } return 0; }
泪奔啊，刚开始想着和单词连接很像，就把那个代码作了一点改动，一直超时，后来 胖子说他做字典树用的并查集。并查集对于大数据量有很快的效率，这个题是25万的数据，看来就是考这点啦。用了并查集，果然过啦
思路：
先把数据存储到字典树里面，字典树再这路的作用有两个：一个是统计颜色种类，一个是每种颜色数量。然后用并查集，讲这些颜色合并。每次输入都合并。到最后统计下 根节点的数量，就是并查集的数量，如果大于1，说明不单单在一个集合，绝对不能连成线，如果是，则要根据 欧拉通路的原理去判定