poj 2513 Colored Sticks （字典树+并查集+欧拉回路）

Colored Sticks

Time Limit : 10000/5000ms (Java/Other)   Memory Limit : 256000/128000K (Java/Other)

Total Submission(s) : 1   Accepted Submission(s) : 1

Problem Description

You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?

 

Input

Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.

 

Output

If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.

 

Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan

 

 

Sample Output

Possible

          

          题目大意：给你很多对单词，单词相当于一个点，一对单词相当于一条边，问这么多对的单词能否组成一条欧拉路，要求每条边都要经过。题目数据很大，每个单词最多10个字母，之前用map映射，把字母映射成编号，但是速度太慢，一直TLE，后来换成字典树，字典树速度才行，连通性就用并查集，判断欧拉路是否组成，就看度数是奇数的个数是否是0或者2。

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

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <map>
using namespace std;

struct node
{
    int x;
    node *next[26];
};

int deg[510005], father[510005], cnt, ant;
node *root, memory[5100050];

node *create()
{
    node *p = &memory[ant++];
    int i;
    for(i = 0; i < 26; i++)
    {
        p->next[i] = NULL;
    }
    return p;
};

void insert(char *s, int x)
{
    node *p = root;
    int i, k;
    for(i = 0; s[i]; i++)
    {
        k = s[i] - 'a';
        if(p->next[k] == NULL)
        {
            p->next[k] = create();
        }
        p = p->next[k];
    }
    p->x = x;
}

int search(char *s)
{
    node *p = root;
    int i, k;
    for(i = 0; s[i]; i++)
    {
        k = s[i] - 'a';
        if(p->next[k] == NULL) return 0;
        p = p->next[k];
	}
    return p->x;
}

void init()
{
    int i;
    for(i = 1; i <= 510000; i++)
    {
        father[i] = i;
    }
    memset(deg, 0, sizeof(deg));
    cnt = 0;
}

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

void Union(int x, int y)
{
    father[x] = y;
}

bool judge()    //判断是否满足欧拉
{
    int i, k, odd = 0;
    for(i = 1; i <= cnt; i++)
    {
        if(deg[i]%2 == 1) odd++;
    }
    if(odd != 0 && odd != 2) return false;
    k = find(1);
    for(i = 2; i <= cnt; i++)
    {
        if(k != find(i)) return false;
    }
    return true;
}

int main()
{
    int x, y, fx, fy;
    char s1[15], s2[15];
    init();
    root = create();
    while(scanf("%s %s", s1, s2) != EOF)
    {
        x = search(s1);     //映射求编号速度太慢
        y = search(s2);     //用字典树来求编号
        if(x == 0) insert(s1, x = ++cnt);
        if(y == 0) insert(s2, y = ++cnt);
        deg[x]++;
        deg[y]++;
        fx = find(x);
        fy = find(y);
        if(fx != fy) Union(fx, fy);
    }
    if(judge()) printf("Possible\n");
    else printf("Impossible\n");

    return 0;
}