欧拉回路

参考:http://www.cnblogs.com/buptLizer/archive/2012/04/15/2450297.html
http://blog.csdn.net/prime_min/article/details/40686563

POJ2513
掌握了一种全新的哈希大法~~
WA了无数发,其实是cnt=0写在node()里去了...
为啥son的深度设为100会错?非要maxn这么大么
420ms+

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 5e5;
const int L = 27;
struct TRIE{
    int son[maxn][L],flag[maxn],id[maxn],tot,root,cnt;
    int node(){
        memset(son[tot],0,sizeof son[tot]);
        flag[tot]=id[tot]=0; 
        return tot++;
    }
    void init(){
        tot=0;cnt=0;
        root=node();
    }
    int getid(char str[]){
        int now=root,idx;
        for(int i = 0; str[i]; i++){
            idx=str[i]-'a';
            if(!son[now][idx]){
                son[now][idx]=node();
            }
            now=son[now][idx];
        }
        if(flag[now]) return id[now];
        flag[now]=1;  return id[now]=++cnt;
    }
}trie;
struct UF{
    int p[maxn];
    void init(){
        for(int i = 0; i < maxn; i++) p[i]=i;
    }
    int find(int x){
        return p[x]==x?x:p[x]=find(p[x]);
    }
    void link(int a,int b){
        a=find(a);b=find(b);
        if(a!=b) p[a]=b;
    }
    bool same(int a,int b){
        return find(a)==find(b);
    }
}uf;
int degree[maxn],n;
char str1[100],str2[100];
int main(){
    trie.init();uf.init();
    while(scanf("%s%s",str1,str2)!=EOF){
        n++;
        int a=trie.getid(str1),b=trie.getid(str2);
        degree[a]++;degree[b]++;
        uf.link(a,b);
    }
    if(trie.flag[trie.root]||trie.tot<2){
        printf("Possible\n");
        return 0;
    }
    int anc=uf.find(1),num=0;
    bool flag=0;
    for(int i = 1; i <= trie.cnt; i++){
        if(!uf.same(i,anc)){
            flag=1;
            break;
        }
        if(degree[i]%2==1) num++;
        if(num>2){
            flag=1;
            break;
        }
    }
    if(num==1) flag=1;
    if(flag) printf("Impossible\n");
    else printf("Possible\n");
    return 0;
}

混合图欧拉回路 poj1637,zju1992,hdu3472
1HDU 3018 Ant Trip
2POJ 1041 John's trip
3 POJ 1386 Play on Words
4 POJ 2230 Watch Cow
5 POJ 2513 Colored Sticks
6 POJ 2337 Catenyms
7 POJ 1392 Ouroboros Snake
8 HDU 2894 DeBruijin
邮递员问题 poj2040 poj2404
哈密顿回路 poj2439 poj2288 poj1392 hdu2894
hdu
3018
1116
2894
1956
3472
参考:http://blog.csdn.net/u013533289/article/details/40985419

标签: 算法, 学习

添加新评论