题目大意:
有n根棍子(n<250000),每根棍子两端都涂上颜色,颜色用长度小于10的字符串表示,问能否将所有的棍子排成一排,使得每两根棍子衔接的地方颜色相同.
分析:
题目很明确,将所有的颜色看做节点.连接两种颜色的棍子看做节点之间的连边.问是否存在一条欧拉通路.
用字典树的目的是给每种颜色编号.用并查集来判断无向图是否连通.最后要做的就是统计每种颜色的出现次数了.
- /*
- PKU2513 Colored Sticks
- */
- #include <stdio.h>
- #include <string.h>
- #include <malloc.h>
- #define clr(a) memset(a,0,sizeof(a))
- #define CN 26
- #define MEM 6000005
- #define M 600005
- int d[MEM], nd;
- int f[M], nf;
- int FindSet(int f[],int i){
- int j=i,t;
- while(j!=f[j]) j=f[j];
- while(i!=f[i]){ t=f[i]; f[i]=j; i=t; }
- return j;
- }
- void UniteSet(int f[],int i,int j){
- int p=FindSet(f,i), q=FindSet(f,j);
- if(p!=q) { f[q]=p; nf++; }
- }
- /*********************************/
- typedef struct DictNode{
- int c;
- char ch;
- struct DictNode *father;
- struct DictNode *next[CN];
- }Dict;
- int CI(char ch){
- return ch-'a';
- }
- Dict mem[MEM]; int memp;
- Dict* newNode(char ch){
- Dict *p=&mem[memp++];
- p->c=0; p->ch=ch;
- p->father=NULL;
- clr(p->next); return p;
- }
- int Insert(Dict *p,char s[]){
- if(!s[0]){
- if(p->c==0) p->c=++nd;
- d[p->c]++; //统计单词出现次数
- return p->c;
- }
- if(p->next[CI(s[0])]==NULL)
- p->next[CI(s[0])]=newNode(s[0]);
- p->next[CI(s[0])]->father=p;
- return Insert(p->next[CI(s[0])],s+1);
- }
- /*******************************************/
- Dict *root;
- int main()
- {
- int i,j,k,odd;
- char s[20],t[20];
- //init
- nd=0; clr(d); memp=0;
- root=newNode(0); nf=0;
- for(i=0;i<M;i++) f[i]=i;
- //input
- while(scanf("%s%s",s,t)!=EOF){
- i=Insert(root,s);
- j=Insert(root,t);
- UniteSet(f,i,j);
- }
- //judge
- odd=0;
- for(i=1;i<=nd;i++) if(d[i]&1) odd++;
- //output
- if((nf+1==nd||nd==0) && odd<=2) puts("Possible");
- else puts("Impossible");
- return 0;
- }