POJ 2513 字符串hash + 判断欧拉回路

题目链接：http://poj.org/problem?id=2513

题目大意：

　　给定最多25000个筷子，两头有颜色（字符串表示），要求判断这些是否可以连成一条直线，要求是只有相同颜色的才可以连接。

分析：

　　这题我居然想了两个晚上都不会！！！！！！！！！！！！！！！！！！！

　　看了题解：.http://blog.sina.com.cn/s/blog_5cd4cccf0100apd1.html

　　注意我看了题解之后一时情急代码居然写wa了，

　　字符串hash我用了字典树，而且只会字典树。

　　判断是否是欧拉回路：

　　1、并查集判断是否连通，用带路径压缩的写法就可以，然后要扫描出根，对每个点在find一下再判断其father是否是扫描出的根：

int root;
for(int i=1;i<=tot;++i) find( i );
for(int i=1;i<=tot;++i) if( fa[i]==i ) { root= i; break; }
for(int i=1;i<=tot;++i)
        if( i!=root && fa[i]!=root ){
                puts("Impossible");
                return 0;
        }

不能全部find后，扫描fa[i] == i的个数，这样是错误的。为什么？我还没想清楚，并查集表示我以前白学了。

　　2、度数的判定，必须是：全部为偶数度数，或只有2个奇数度数;

当然：

aa aa

bb bb这种是全部是偶数度数的，但是不连通在1那里就会判断出来。

代码（很搓）：

poj2513

 1 /*2513    Accepted    61044K    500MS    C++    2050B    2012-07-18 08:18:52*/
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <vector>
 8 using namespace std;
 9 
10 #define mpair make_pair
11 #define pii pair<int,int>
12 #define MM(a,b) memset(a,b,sizeof(a));
13 typedef long long lld;
14 typedef unsigned long long u64;
15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;}
16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;}
17 #define maxn
18 
19 int size, tot;
20 struct Node{
21     int id, next[26];
22     void init(){
23         id= 0;
24         MM( next, 0 );
25     }
26 }node[1000000];
27 int insert(char *s){
28     int p= 0;
29     while( *s ){
30         int c= *s++-'a';
31         if( !node[p].next[c] ){
32             node[size].init();
33             node[p].next[c]= size++;
34         }
35         p= node[p].next[c];
36     }
37     if( !node[p].id ) node[p].id= ++tot;
38     return node[p].id;
39 }
40 
41 char c1[13], c2[13];
42 int d[500020];
43 int a[250010], b[250010];
44 int fa[500020];
45 
46 int find(int x){
47     if( x==fa[x] ) return x;
48     else return fa[x]= find( fa[x] );
49 }
50 
51 int main()
52 {
53     //freopen("poj2513.in","r",stdin);
54     node[0].init();
55     size= 1;
56     tot= 0;
57     int n= 0;
58     MM( d, 0 );
59     while( scanf("%s%s", c1, c2 ) !=EOF ){
60         ++n;
61         a[n]= insert( c1 );
62         b[n]= insert( c2 );
63         ++d[ a[n] ];
64         ++d[ b[n] ];
65     }
66 
67     // judge if the graph is connected;
68     for(int i=1;i<=tot;++i) fa[i]= i;
69     for(int i=1;i<=n;++i){
70         int fx= find( a[i] );
71         int fy= find( b[i] );
72         if( fx!=fy )
73             fa[fx]= fy;
74     }
75     int root;
76     for(int i=1;i<=tot;++i) find( i );
77     for(int i=1;i<=tot;++i)if( fa[i]==i ){root= i;break;}
78     for(int i=1;i<=tot;++i)
79         if( i!=root && fa[i]!=root ){
80             puts("Impossible");
81             return 0;
82         }
83 
84     // judge the degree of each node;
85     cnt= 0;
86     for(int i=1;i<=tot;++i)
87         if( d[i]&1 )
88             ++cnt;
89     if( 0==cnt || 2==cnt ) puts("Possible");
90     else puts("Impossible");
91 }

一毛原创作品，转载请注明出处。