Colored Sticks (POJ 2513)
Time Limit: 5000MS Memory Limit: 128000K

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
Hint

Huge input,scanf is recommended.

解题思路：使用字典树（Trie）与并查集（Union-Find）数据结构

#include <stdio.h>
#include <string.h>
#define MAXN 610000
typedef struct Trie
{
    int child[30];
    int isStr;
    int num;
}Trie;

int root, pCur;
Trie arr[MAXN];

char c1[20],c2[20];

int pi[MAXN],rank[MAXN],cap[MAXN];

int Find(int i)
{
    while (pi[i] != 0)
    {
        i = pi[i];
    }
    return i;
}

void Merge(int i, int j)
{
    i = Find(i);
    j = Find(j);
    if (i != j)
    {
        if (rank[i] > rank[j])
        {
            pi[j] = i;
        }
        else
        {
            pi[i] = j;
            if (rank[i] == rank[j])
            {
                rank[j] ++;
            }
        }
    }
}
int main()
{
    int len,i,j;
    int ca,cb;
    int total = 0;
    int amt = 0;
    int jdg,flag;
    int one;
    root = amt ++;

    while (scanf("%s%s",c1,c2) != EOF)
    {
        pCur = root;
        len = strlen(c1);
        for (i = 0; i < len; i ++)
        {
            if (arr[pCur].child[c1[i] - 'a'] == 0)
            {
                arr[pCur].child[c1[i] - 'a'] = amt ++;
            }
            pCur = arr[pCur].child[c1[i] - 'a'];
            if (i == len - 1)
            {
                if (arr[pCur].isStr == 0)
                {
                    arr[pCur].isStr = 1;
                    arr[pCur].num = total ++;
                }
                ca = arr[pCur].num;
                cap[ca] ++;
            }
        }
        pCur = root;
        len = strlen(c2);
        for (i = 0; i < len; i ++)
        {
            if (arr[pCur].child[c2[i] - 'a'] == 0)
            {
                arr[pCur].child[c2[i] - 'a'] = amt ++;
            }
            pCur = arr[pCur].child[c2[i] - 'a'];
            if (i == len - 1)
            {
                if (arr[pCur].isStr == 0)
                {
                    arr[pCur].isStr = 1;
                    arr[pCur].num = total ++;
                }
                cb = arr[pCur].num;
                cap[cb] ++;
            }
        }

        Merge(ca,cb);
    }

    flag = 1;
    jdg = Find(0);
    for (i = 1; i < total; i ++)
    {
        if (Find(i) != jdg)
        {
            //printf("Crush %d %d\n",Find(i),jdg);
            flag = 0;
            break;
        }
    }
    one = 0;
    if (flag)
    {
        for (i = 0; i < total; i ++)
        {
            //printf("cap[%d] %d\n",i+1,cap[i]);
            if (cap[i] % 2)
                one ++;
            if (one > 2)
            {
                flag = 0;
                break;
            }
        }
    }
    if (one == 1)
        flag = 0;

    if (flag)
    {
        puts("Possible");
    }
    else
    {
        puts("Impossible");
    }
    return 0;
}

本文链接：http://bookshadow.com/weblog/2014/05/03/poj-2513/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码