nyoj 230 페인트 막대 및 사전 트리 찾기 오라

1

5

blue red

red violet

cyan blue

blue magenta

magenta cyan

Possible

#include<stdio.h>

#include<string.h>

#include<malloc.h>

struct node

{

    int order;

    struct node *next[26];

};



int  t;// 

int father[250001];// 

int degree[250001];// 

int insert(char *str,node *T)// 

{

    int len,id,flat=0,i,j;

    node *p,*q;

    len=strlen(str);

    p=T;

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

    {

        id=str[i]-'a';

        if(p->next[id]==NULL)

        {

            flat=1;

            q=(node *)malloc(sizeof(node));

            for(j=0;j<26;++j)

                q->next[j]=NULL;

            p->next[id]=q;

        }

        p=p->next[id];

    }

    if(flat)// ， 

    {

        p->order=t;//   

        degree[t++]++;// 

        return p->order;

    }

    else

    {

        if(p->order==0)//  abdse abd ， 

        {

            p->order=t;

            degree[t++]++;

            return p->order;

        }

        degree[p->order]++;

        return p->order;

    }

}



int findfather(int i)

{

    if(father[i]==-1)

        return i;

    else

        return findfather(father[i]);

}



void merge(int a,int b)//  

{

    a=findfather(a);

    b=findfather(b);

    if(a!=b)

    {

        if(father[a]<father[b])

            father[b]=a;

        else

            father[a]=b;

    }

}



int main()

{

    char str1[14],str2[14];

    int flag,i,num1,num2,n,x;

    node *T;

    scanf("%d",&x);

    while(x--)

    {

        T=(node *)malloc(sizeof(node));

        T->order=0;

        memset(degree,0,sizeof(degree));

        memset(father,-1,sizeof(father));

        for(i=0;i<26;++i)

            T->next[i]=NULL;

        t=1;

        scanf("%d",&n);

        if(n==0)

        {

            printf("Possible
");

            continue;

        }

        while(n--)

        {

            scanf("%s%s",str1,str2);

            num1=insert(str1,T);

            num2=insert(str2,T);

            merge(num1,num2);

        }

        flag=0;

        for(i=1;i<t;++i)

            if(father[i]==-1)// 

                ++flag;

        if(flag>1)

            printf("Impossible
");

        else

        {

            flag=0;

            for(i=1;i<t;++i)

                if(degree[i]&1)

                    flag++;

            if(flag==2||flag==0)

                 printf("Possible
");

            else

                 printf("Impossible
");

        }

    }

    return 0;

}