POJ-2513 Colored Sticks【并查集+Trie+Euler路】

タイトルリンク:http://poj.org/problem?id=2513
 
テーマ:
N本の木の棒があって、1本の木の棒は2つの头があって、私达はすべての头を色(同じか异なっています)を涂って、もし2本の木の棒は同じ色の一端が接続することができるならば、色はすべて异なって接続することができなくて、今あなたにN本の木の棒とそれらの色をあげて、最后に1本のチェーンにリンクすることができますかを闻きます.
 
問題解決の考え方:
本質的にはオーラルな問題ですが、色が文字列なので簡単には処理できません(mapでタイムアウトします～.～)ので、1つの方法で単語ごとに1つの数字に変換して、典型的なオーラルな問題になるはずです.
ディクショナリツリーを使用して色を処理し、色ごとに1つの値を返し、連通図+Eulerで解決すればよいと判断します.
元々書かれていたpre配列はpre[i]=iであり,最適化後はpre[i]=−1となり,memsetを値付けする際に速度を速めることができる.そしてFind_Setは再帰+経路圧縮を採用し,insertは配列の下付きを返し,辞書ツリーは静的配列を採用し,速度を速めた.最適化後の速度は900+msから400+msに変化した.
 
コードは次のとおりです.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

#define CLR(arr, what) memset(arr, what, sizeof(arr))
const int N = 15;
const int M = 1000010;

struct Trie
{
	int num;
	Trie* next[26];
}*Head;

char u[N], v[N];
int num, n, top, total;
bool flag;
int pre[M], in[M];
Trie trie[M];

int Find_Set(int x) //  +    
{
	return pre[x] == -1 ? x : (pre[x] = Find_Set(pre[x]));
}

void Make_Set(int x, int y) //     
{
	int root1 = Find_Set(x);
	int root2 = Find_Set(y);
	if(root1 != root2)
		pre[root2] = root1;
}

int insert(char str[]) //      
{
	Head = &trie[0];
	int len = strlen(str);
	for(int i = 0; i < len; ++i)
	{
		int temp = str[i] - 'a';
		if(Head->next[temp] == NULL)
			Head->next[temp] = &trie[++num];
		Head = Head->next[temp];
	}
	if(Head->num == 0)
		Head->num = top++;
	return Head->num;
}

void init()
{
	num = total = 0; top = 1; flag = true;
	CLR(in, 0); CLR(pre, -1);
	for(int i = 0; i < 2 * n + 2; ++i)
	{
		trie[i].num = 0;
		for(int j = 0; j < 26; ++j)
			trie[i].next[j] = NULL;
	}
}

int main()
{
	int tmp, temp;
	init();
	while(scanf("%s %s", &u, &v) != EOF)
	{
		tmp = insert(u); temp = insert(v);
		in[tmp]++; in[temp]++;
		Make_Set(tmp, temp);
	}
	int root = Find_Set(1);
	for(int i = 1; i < top; ++i) //    +     
	{
		if(root != Find_Set(i))
		{
			flag = false;
			break;
		}
		if(in[i] & 1)
			total++;
		if(total > 2)
			break;
	}
	puts(((total == 0 || total == 2) && flag == true) ? "Possible" : "Impossible");
	return 0;
}