POJ训练计划_Colored Sticks(字典树+判断欧拉通路)

解题报告

http://blog.csdn.net/juncoder/article/details/38236333

题目传送门

题意：

问给定一堆的棒，两端有颜色，相同的颜色的棒可以头尾相接，能否连在一条直线。

思路：

把每一根棒两端看成两个点，之间连着线，判断这样的一个图中是否有欧拉通路

欧拉通路：

在联通无向图中，经过G的每一条边一次并且仅有一次的路径为欧拉通路。

求欧拉通路的充分条件：图为联通图，并且仅有两个奇度数的结点或无奇度结点。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; struct node { int v; node *next[30]; }; int d[251000*2],cnt,B[251000*2]; node *newnode() { node *p=new node; p->v=0; for(int i=0; i<26; i++) { p->next[i]=NULL; } return p; } void addnode(node *root,char *str,int nn) { node *p=root; int l=strlen(str),i; for(i=0; i
      
       next[t]==NULL) p->next[t]=newnode(); p=p->next[t]; } p->v=nn; } int findd(node *root,char *str) { node *p=root; int l=strlen(str),i; for(i=0; i
       
        next[t]==NULL) return 0; p=p->next[t]; } return p->v; } int bfind(int x) { if(B[x]!=x) B[x]=bfind(B[x]); return B[x]; } void bin(int x,int y) { int xx=bfind(x); int yy=bfind(y); if(xx!=yy) { B[xx]=yy; } } int main() { int a,b,i,j; node *root=newnode(); char str1[100],str2[100]; cnt=1; for(i=0; i<=250000*2; i++) B[i]=i; while(~scanf("%s%s",str1,str2)) { a=findd(root,str1); b=findd(root,str2); if(!a) { addnode(root,str1,cnt); a=cnt++; } d[a]++; if(!b) { addnode(root,str2,cnt); b=cnt++; } d[b]++; } int sum=0,sum2=0; for(i=1; i
        
         1) { printf("Impossible\n"); } else { if(sum2==2||sum2==0) printf("Possible\n"); else printf("Impossible\n"); } } 
        
       
      
     
    
   
  

Description

Input

Output

Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan

Sample Output

Possible

Hint