周赛-Colored Sticks 分类：比赛 ...-白红宇

周赛-Colored Sticks 分类：比赛 ...

阅读量：4664 次

发布时间：2019-06-09

本文共 2169 字，大约阅读时间需要 7 分钟。

Colored Sticks

Time Limit: 5000MS Memory Limit: 128000K

Total Submissions: 32423 Accepted: 8556

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

字典树+并查集+欧拉路径

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #define LL long long#define RR freopen("output.txt","r",stdoin)#define WW freopen("input.txt","w",stdout)using namespace std;const int MAX = 2500000;struct node{ int num; node *next[26];}head;int pre[MAX];int Du[MAX];int top;char s[15],c[15];node *Creat(){ node *p; p=new node; p->num=0; for(int i=0;i<26;i++) { p->next[i] = NULL; } return p;}int Build_Tree(char *str)//建立字典树{ int len=strlen(str); int a; node *p=&head; for(int i=0;i
               
                next[a]) { p=p->next[a]; } else { p->next[a]=Creat(); p=p->next[a]; } } if(!p->num)//返回单词所在的位置 { p->num=++top; } return p->num;}int Find(int x)//并查集+压缩路径{ int i=x,j=x,s; while(pre[i]!=-1) { i=pre[i]; } while(pre[j]!=-1) { s=pre[j]; pre[j]=i; j=s; } return i;}void Link(int x,int y){ int FX=Find(x); int FY=Find(y); if(FX!=FY) { pre[FX]=FY; }}int main(){ memset(pre,-1,sizeof(pre)); memset(Du,0,sizeof(Du)); top=0; for(int i=0;i<26;i++) { head.next[i]=NULL; } // int n; // scanf("%d",&n); //for(int i=0;i
                
                 1||ans>2)//如果入度为奇数的超过2个，或者根大于一个就不能连成一条直线 { break; } } if(ant>1||ans>2) { printf("Impossible\n"); } else { printf("Possible\n"); } return 0;}

转载于:https://www.cnblogs.com/juechen/p/4721941.html

你可能感兴趣的文章