题意:给出很多很多很多很多个棒子 左右各有颜色(给出的是单词) 相同颜色的可以接在一起,问是否存在一种
方法可以使得所以棒子连在一起
思路:就是一个判欧拉通路的题目,欧拉通路存在:没奇度顶点 或者只有2个奇度顶点 同时要连通 。关键在于给颜色hash和
判断连通性 hash用字典树 连通用并查集
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 const int maxn=520000+20; 6 struct Trie{ 7 int ch[maxn][26]; 8 int size; 9 int num[maxn]; 10 int number; 11 void init(){ 12 memset(ch,0,sizeof(ch)); 13 size=1; 14 number=1; 15 memset(num,0,sizeof(num)); 16 } 17 void insert(char*s){ 18 int rc=0,i=0; 19 for(;s[i]!='