Colored Sticks（字典树+并查集+欧拉通路）（POJ 2513）

题目大意

       有若干根$(\leq 250000)$(≤250000)木棍，每根木棍的两端都有一个颜色（每个颜色用长度$\leq 10$≤10的小写字母串表示），问是否能够将这些木棍拼接成一根木棍，且位于同一相交处的两个颜色是相同的？

分析过程

       这道题的做法有一个比较巧妙的思路转换过程。我们发现，如果以不同的颜色作为顶点，将每根木棍对应于连接某两个顶点的一条边，我们可以得到一个图。那么此时，这个问题就转化为了能否在这张图上找到一个“一笔画”路径，即欧拉通路，容易想到，这是与原问题等价的问题。因此，我们需要建图，判断图的连通性（这里使用并查集），然后判断是否存在一个欧拉通路即可（根据下面的判定定理）。
       欧拉图判定定理——无向连通图G 含有欧拉通路，当且仅当 G 有零个或两个奇数度的结点。
       在建图的时候我们发现需要先将颜色映射为整数以表示顶点，在这里如果我们使用$STL$STL中的$map$map进行标记的话，在这道题目中会超时（毒瘤出题人 ），我们注意到这道题把颜色字符串的长度限定在了$10$10以内，因此我们可以借助字典树来实现这种关系映射，在插入字典树时判断该字符串是否存在，不存在则新建一个颜色顶点，每一次插入的时间复杂度为$O(logL)$O(logL)(L为插入字符串的长度)，而$map$map每一次插入的时间复杂度为$O(logN)$O(logN)(N为字符串数量)。因此在这个问题情境下字典树的效率是要比$map$map高的。

AC代码

#include<iostream>
#include<vector>
#include<cstring>
#include<string>
//#include<map>
using namespace std;
const int maxn = 5e5 + 100;
typedef long long ll;
int tot, cnt;
int tree[maxn][27];
int r[maxn]; //并查集数组 
int flag[maxn];
vector<int> G[maxn];
//map<string, int> mp; //map TLE 
void init(){
	int i;
	for(i=1;i<=500000;++i) r[i] = i;
}
int insert(char *str, int len){ //插入字典树并返回结尾字符节点编号 
	int i, root = 0;
	for(i=0;i<len;++i){
		int e = str[i] - 'a';
		if(!tree[root][e]) tree[root][e] = ++tot;
		root = tree[root][e];
	}
	if(!flag[root]) flag[root] = ++cnt; //节点编号 
	return flag[root];
}
int find(int cur){
	if(cur == r[cur]) return cur;
	return r[cur] = find(r[cur]);
}
void combine(int x, int y){
	int px = find(x), py = find(y);
	if(px != py){
		r[px] = py;
	}
}
bool solve(){
	int i, j = find(1), ans = 0;
	for(i=2;i<=cnt;++i){ //并查集判断图是否连通 
		if(find(i) != j) break;
	}
	if(i <= cnt) return false;
	for(i=1;i<=cnt;++i){ //判断奇数度顶点个数 
		if(G[i].size() & 1) ++ans;
	}
	if(!ans || ans == 2) return true;
	return false;
}
int main(){
	int i, j;
	char str1[15], str2[15];
	ios::sync_with_stdio(false);
	init();
	while(cin>>str1>>str2){
		int u = insert(str1, strlen(str1)), v = insert(str2, strlen(str2));
		G[u].push_back(v);
		G[v].push_back(u);
		combine(u, v);
	}
	if(solve()){
		cout<<"Possible";
	}else{
		cout<<"Impossible";
	}
	return 0;
}