首页 > 代码库 > poj2513Colored Sticks(欧拉通路+字典树+并查集)

poj2513Colored Sticks(欧拉通路+字典树+并查集)

2024-07-14 04:10:10   222人阅读

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.
解题：欧拉通路定义：在一个连通图G中，每条边只经过一次，一次性走完所有的边。
    欧拉通路判断：每个顶点的度数全为偶数或恰好只有两个顶点的度数为奇数。
那么这题要是接成一条线，也就是每条边只用一次，正合欧拉通路定义。 用并查集来判断所有的边是不是组成一个连能图，字典树
来计算顶点的个数及每个顶点出现的次数（计算奇偶数）。
注意：这题数据有空输入，那么也是possible.
#include<stdio.h>
typedef struct nn
{
    int flag;
    int indx;
    struct nn *next[26];
}node;
node *builde()
{
    node *p=new node;
    p->flag=0;
    for(int i=0;i<26;i++)
    p->next[i]=NULL;
    return p;
}
node *root;
int jdn;//计算顶点为奇数的个数
int insert(char str[],int n)
{
    node *p=root;
    for(int i=0;str[i]!='\0';i++)
    {
        if(p->next[str[i]-'a']==NULL)
        p->next[str[i]-'a']=builde();
        p=p->next[str[i]-'a'];
    }
    if(p->flag==0)
    p->indx=n;
    p->flag++;
    if((p->flag)%2)jdn++;else jdn--;
    return p->indx;
}

int fath[5100000],dn;//dn为边数和点数之差
int findfather(int x)
{
    if(x!=fath[x])
    fath[x]=findfather(fath[x]);
    return fath[x];
}
void set(int a,int b)
{
    a=findfather(a);
    b=findfather(b);
    if(a!=b)
    {
        dn--; fath[a]=b;
    }
}
int main()
{
    char c1[1000],c2[1000];
    int n=0,a,b;
    dn=0; jdn=0;
    root=builde();
    while(scanf("%s%s",c1,c2)>0)
    {
        a=insert(c1,n+1);
        if(a==n+1)
        {
            dn++; n++; fath[n]=n;
        }
        b=insert(c2,n+1);
        if(b==n+1)
        {
            dn++; n++; fath[n]=n;
        }
        set(a,b);
    }
    if((jdn==2||jdn==0)&&dn==1||n==0)
    printf("Possible\n");
    else
    printf("Impossible\n");
}



联系
我们