POJ 2513 trie树+并查集判断无向图的欧拉路

生无可恋

查RE查了一个多小时。。

原因是我N define的是250500

应该是500500！！！！！！！！！

身败名裂，已无颜面对众人。。

吐槽完了 我们来说思路。。。

思路：

判有向图能否形成欧拉路

但是他给的是string，怎么转化成int呢？

trie树！

这东西有多么优美我就不说了。。。

反正写起来不难。

具体的请见代码吧

// by SiriusRen

#include <bitset>

#include <cstdio>

#define N 500500

using namespace std;

bitset<N>b;

int tot=0,num=0,f[N],n,m,ansx=0,ans=0,v[N],trie[N*10][27];

int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

int get(){

    int jy=0;char p=getchar();

    if(p==EOF)return 0;

    while(p>'z'||p<'a')p=getchar();

    while(p>='a'&&p<='z'){

        if(trie[jy][p-'a']==-1){

            trie[jy][p-'a']=++tot;

            jy=trie[jy][p-'a'];

            for(int i=0;i<26;i++)trie[jy][i]=-1;

        }

        else jy=trie[jy][p-'a'];

        p=getchar();

    }

    if(!trie[jy][26])return trie[jy][26]=++num;

    else return trie[jy][26];

}

int main(){

    for(int i=0;i<26;i++)trie[0][i]=-1;

    for(int i=1;i<=500000;i++)f[i]=i;

    while(n=get()){

        m=get();

        v[m]++;v[n]++;

        f[find(n)]=find(m);

    }

    for(int i=1;i<=num;i++)

        if(!b[find(i)])b[find(i)]=1,ans++;

    for(int i=1;i<=num;i++)

        if(v[i]&1)ansx++;

    if(ans<=1&&(ansx==0||ansx==2))puts("Possible");

    else puts("Impossible");

}

这一版都是我刷的。。。。包括vjudge。。。。。。