POJ2513 Colored Sticks(Trie+欧拉回路)

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
题意:给你n(n<=250000)根小木棒,木棒两端染有一些颜色,两根木棒相连需要保证相连端点颜色一致.求这些木棒是否可以全部相连?
题解:可以将木棒理解为边,连接两种颜色,那么全部相连就变成了一笔画的问题,即判断欧拉回路.
欧拉回路需要满足两个条件:
1.度数为奇数的点为0个或2个
2.图联通
现在的问题是如何把字符串变成数字的点,用map是肯定会TLE的
hash应该可以,但tire好写,所以我选择了trie树,存入trie的值为该字符串的映射
图联通用并查集去判断.
代码如下:

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int cnt=,du[],fa[];

struct Trie

{

    int sz,tr[][];

    int time[];

    void clear()

    {

        sz=;

        memset(tr,,sizeof(tr));

    }

    void insert(char* c,int x)

    {

        int rt=,len=strlen(c);

        for(int i=;i<len;i++)

        {

            if(!tr[rt][c[i]-'a'])

            {

                tr[rt][c[i]-'a']=++sz;

            }

            rt=tr[rt][c[i]-'a'];

        }

        time[rt]=x;

    }

    int search_t(char *c)

    {

        int rt=,len=strlen(c);

        for(int i=;i<len;i++)

        {

            if(!tr[rt][c[i]-'a'])

            {

                return ;

            }

            rt=tr[rt][c[i]-'a'];

        }

        return time[rt];

    }

}trie;

void mem(int n)

{

    for(int i=;i<=n;i++)

    {

        fa[i]=i;

    }

}

int find(int x)

{

    if(x!=fa[x])

    {

        fa[x]=find(fa[x]);

    }

    return fa[x];

}

void union_(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx!=fy)

    {

        fa[fx]=fy;

    }

}

int euler()

{

    int sum=,t=find();

    for(int i=;i<=cnt;i++)

    {

        if(du[i]%==)

        {

            sum++;

        }

    }

    if(sum!=&&sum!=)

    {

        return ;

    }

    for(int i=;i<=cnt;i++)

    {

        if(find(i)!=find(t))

        {

            return ;

        }

    }

    return ;

}

int main()

{

    char s1[],s2[];

    mem();

//    freopen("1.in","r",stdin);

//    freopen("1.out","w",stdout);

    while(scanf("%s %s\n",s1,s2)!=EOF)

    {

        int from,to;

        if(!trie.search_t(s1))

        {

            trie.insert(s1,++cnt);

        }

        from=trie.search_t(s1);

        du[from]++;

        if(!trie.search_t(s2))

        {

            trie.insert(s2,++cnt);

        }

        to=trie.search_t(s2);

        du[to]++;

        union_(from,to);

    }

    if(euler())

    {

        puts("Possible");

    }

    else

    {

        puts("Impossible");

    }

}

巴特西

POJ2513 Colored Sticks(Trie+欧拉回路)

最新文章

热门文章