POJ_2513_Colored Sticks（欧拉路+字典树）

Description

Input

Output

Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan

Sample Output

Possible

题意：给你一些个木棒，每根木棒两端都着了 色，问能否将它们排成一条线，使得接触点的颜色是一样的。

解析：很明显的求欧拉路问题。一开始用map转化超时，后来去学了用字典树的方法处理。值得注意的是，trie数组得开足够大，我是开550000。反正在这个数组上面RE了n次心都碎了。

题目链接：http://poj.org/problem?id=2513

代码清单：

#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<ctime>
#include<cctype>
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

struct edge{
    int point;
    int letter[30];
}trie[550000];
int number=0,Point=0;
int father[550000];
char s1[15],s2[15];
int degree[550000];

int Find(int x){
    if(x!=father[x]) return Find(father[x]);
    return father[x];
}

int GetPoint(char s[]){
    int j=0;
    int len=strlen(s);
    for(int i=0;i<len;i++){
        if(trie[j].letter[s[i]-'a'])
            j=trie[j].letter[s[i]-'a'];
        else{
            trie[j].letter[s[i]-'a']=++number;
            j=number;
        }
    }
    if(trie[j].point==0) trie[j].point=++Point;
    return trie[j].point;
}

bool IsEuler(int n){
    int cnt=0,temp=0;
    for(int i=1;i<=n;i++){
        if(father[i]==i) cnt++;
        if(degree[i]%2)  temp++;
    }
    if(cnt>1) return false;
    else{
        if(temp==0||temp==2) return true;
        else return false;
    }
}

int main(){
    memset(trie,0,sizeof(trie));
    memset(degree,0,sizeof(degree));
    for(int i=0;i<550000;i++) father[i]=i;
    //freopen("liuchu.txt","r",stdin);
    while(scanf("%s%s",s1,s2)!=EOF){
        int point1=GetPoint(s1);
        int point2=GetPoint(s2);
        degree[point1]++;
        degree[point2]++;
        point1=Find(point1);
        point2=Find(point2);
        father[point1]=point2;
    }
    if(IsEuler(Point)) printf("Possible\n");
    else printf("Impossible\n");
    return 0;
}

POJ_2513_Colored Sticks（欧拉路+字典树）

原文：http://blog.csdn.net/jhgkjhg_ugtdk77/article/details/44581417