本文主要是介绍poj -2513-Colored Sticks-哈希并查集或者字典树并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你任意条木棍，读到文件结束输入结束，木棍两边有颜色，相同颜色的可以连到一起，问是否可以连成一个欧拉路，这道题看着有两种做法
1. 哈希&并查集
做法是字符串哈希，去判断奇数度的个数，个数大于等于3的话是代表不能形成一个欧拉路的，小于3的话，就看一下并查集，看是否这几个点是一个图上的，
2. 字典树&并查集
做法略显麻烦，原因在于建字典树吧，其他的与上遍的做法相似，也是找奇数度和并查集啊
1 哈希： 563ms
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 500005
int f[maxn+10];
int degree[maxn+10];
int find(int x)
{return f[x] == x ? x : f[x] = find(f[x]);
}
void bc(int x,int y)
{int xx = find(x);int yy = find(y);if(xx == 0)f[x] = x;if(yy == 0)f[y] = y;f[find(x)]=find(y);
}
int hash_index(char s[])
{int hash=1;int len=strlen(s);for(int i=0; i<len; i++)hash=(hash*29+s[i]-'a')%maxn;return hash;
}int main()
{char s[15], t[15];for(int i = 0; i <= maxn; i++){f[i] = 0;degree[i] = 0;}while(~scanf("%s%s",s,t)){int sh = hash_index(s);int th = hash_index(t);degree[sh]++;degree[th]++;bc(sh,th);}int cont = 0;for(int i = 0; i <= maxn; i++){if(degree[i]%2)cont++;if(cont > 2){printf("Impossible\n");return 0;}}int i = 1;while(i <maxn &&find(i)==0)i++;int flag = find(i);for(;i < maxn ; i++){int x = find(i);if(x&&x!=flag){printf("Impossible\n");return 0;}}printf("Possible\n");return 0;
}
这里有字符串哈希的资料： 哈希字符串
2.字典树
转载：看着写的挺简洁明了的，就果断转了，这个动态的，跑1791ms;用数组模拟链表的话会更慢，
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=500005;
int degree[maxn];
int p[maxn];
int num;
struct node
{int id;node *next[26];node (){id=-1;for(int i=0; i<26; i++)next[i]=NULL;}
}*root;
int find_p(int x)
{while(p[x]!=x)x=p[x];return x;
}
void merge(int x,int y)
{p[find_p(x)]=find_p(y);
}
int insert(char s[])
{int i,j;node *p=root;int len=strlen(s);for(i=0; i<len; i++){if(p->next[s[i]-'a']==NULL)p->next[s[i]-'a']=new node;p=p->next[s[i]-'a'];}if(p->id==-1)p->id=num++;return p->id;
}
int main()
{num=0;root=new node;char a[11],b[11];int id1,id2;int i;for(i=0; i<maxn; i++){degree[i]=0;p[i]=i;}while(scanf("%s%s",a,b)!=EOF){id1=insert(a);id2=insert(b);degree[id1]++;degree[id2]++;merge(id1,id2);}int sum=0;int flag=find_p(0);for(i=0; i<num; i++){if(degree[i]%2)sum++;if(sum>2||flag!=find_p(i)){printf("Impossible\n");return 0;}}printf("Possible\n");return 0;
}这篇关于poj -2513-Colored Sticks-哈希并查集或者字典树并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
