poj 2513 Colored Sticks 彩色棒

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <cstdio>
  6 #include <cstring>
  7 #include <cmath>
  8 #include <stack>
  9 #include <queue>
 10 #include <functional>
 11 #include <vector>
 12 #include <map>
 13 using namespace std;
 14 #define M 0x0f0f0f0f
 15 #define min(a,b) (a>b?b:a)
 16 #define max(a,b) (a>b?a:b)
 17 int cnt=1;//单词的个数
 18 int father[500002];
 19 int v[500002];
 20 struct tree
 21 {
 22     struct tree *next[30];
 23     int ji;//标记该结点处是否构成单词，还代表该单词的编号
 24 };
 25 int insert_(struct tree *root,char *s)//通过trie树对每一种颜色进行编号
 26 {
 27     int i;
 28     if(*s==‘\0‘||root==NULL)
 29         return 0;
 30     struct tree *p=root;
 31     while(*s!=‘\0‘)
 32     {
 33         if(p->next[*s-‘a‘]==NULL)
 34         {
 35             struct tree *t=(struct tree *)malloc(sizeof(struct tree));
 36             for(i=0; i<30; i++)
 37             {
 38                 t->next[i]=NULL;
 39             }
 40             t->ji=0;
 41             p->next[*s-‘a‘]=t;
 42             p=t;
 43         }
 44         else
 45             p=p->next[*s-‘a‘];
 46         s++;
 47     }
 48     if(p->ji==0)
 49         p->ji=cnt++;
 50     return p->ji;
 51 }
 52 
 53 //并查集，判断是否联通
 54 void inte()
 55 {
 56     for(int i=0; i<500003; i++)
 57         father[i]=i;
 58 }
 59 
 60 int find_(int a)
 61 {
 62     if(father[a]==a)
 63         return a;
 64     return find_(father[a]);
 65 }
 66 
 67 void unin(int a,int b)
 68 {
 69     int a1=find_(a);
 70     int b1=find_(b);
 71     if(a1!=b1)
 72         father[a1]=b1;
 73 }
 74 
 75 int main()
 76 {
 77     int a1,b1;
 78     char a[13],b[13];
 79     int i;
 80     struct tree *root=(struct tree *)malloc(sizeof(struct tree));
 81     for(i=0; i<30; i++)
 82         root->next[i]=NULL;
 83     root->ji=0;
 84     memset(v,0,sizeof(v));
 85     inte();
 86     while(scanf("%s %s",a,b)!=EOF)
 87     {
 88         a1=insert_(root,a);
 89         b1=insert_(root,b);
 90         v[a1]++;
 91         v[b1]++;
 92         unin(a1,b1);
 93     }
 94     int mm=find_(1);
 95     int flag=0;
 96     int flag1=0;
 97     if(v[1]%2)
 98         flag1++;
 99     for(i=2; i<cnt; i++)
100     {
101         if(mm!=find_(i))
102             flag=1;
103         if(v[i]%2)
104         {
105             flag1++;
106         }
107     }
108 
109     if(flag)//bu lian tong
110         printf("Impossible\n");
111     else if(flag1==0||flag1==2)//ke yibi hua
112         printf("Possible\n");
113     else
114         printf("Impossible\n");
115     return 0;
116 }