POJ2513 Colored Sticks（字典树+并查集+欧拉通路）

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

一道题用到三个知识点

先用字典树对每个单词进行映射为数字，然后用并查集判断是否都在一个组，最后判断是否存在欧拉通路

字典树

一篇讲字典树的博客：https://blog.csdn.net/weixin_39778570/article/details/81990417

先定义一个二维数组Trie[MaxSize][26]；k=1  //26是小写字母个数，可自定义

建树：

void insertt(char *s)//处理字符串
{
    int len=strlen(s);
    int p=0;
    for(int i=0;i<len;i++)
    {
        int c=s[i]-'a';
        if(trie[p][c]==0)
        {trie[p][c]=k;
        k++;}
        p=trie[p][c];
    }
    color[p]=1;
}

查询：

int searchh(char *s)
{
    int len=strlen(s);;
    int p=0;
    for(int i=0;i<len;i++)
    {
        int c=s[i]-'a';
        if(trie[p][c]==0)
        {return 0;}
        p=trie[p][c];
    }
    return color[p]==1;
}

并查集略。。。。。

欧拉回路

欧拉通路就是给一个图，存在一条通路把所边经过且每条边只经过一次。

对于无向图：

1、存在欧拉通路的条件：每个点的度都为偶数；

2、存在欧拉通路的条件：有且只有两个点的度为一，且这两个点分别为起点和终点；

对于有向图：

1、存在欧拉通路的条件：每个点出度等于入度；

2、存在欧拉路的条件：存在一个点出度比入度多一作为起点，存在一点入度比出度多一作为终点，其余点出度等于入度；

求欧拉通路的方法——基本（套圆）法

DFS搜索，不能再往下走便回溯，回溯时记录路径，回溯时不清除对边的标记，最后求出来的路径就是欧拉回路。

原题代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int trie[5000100][26];
int color[5000100];
int f[5000100];
int k=1;
int cnt=0;//不同颜色的个数
int d[5000100];//存度，判断欧拉通路
//字典树///////////////////////////////
void insertt(char *s)
{
    int len=strlen(s);
    int p=0;
    for(int i=0;i<len;i++)
    {
        int c=s[i]-'a';
        if(trie[p][c]==0)
        {trie[p][c]=k;
        k++;}
        p=trie[p][c];
    }
    color[p]=++cnt;
}
int searchh(char *s)
{
    int len=strlen(s);;
    int p=0;
    for(int i=0;i<len;i++)
    {
        int c=s[i]-'a';
        if(trie[p][c]==0)
        {return 0;}
        p=trie[p][c];
    }
    if(color[p]>0)
    {return color[p];}
    else
    {return 0;}
}
//并查集/////////////////////////////
void init()
{
    for(int i=0;i<=500010;i++)
    {f[i]=i;}
}
int getf(int t)
{
    if(f[t]==t)
    {return t;}
    else
    {
        f[t]=getf(f[t]);
        return f[t];
    }
}
void sett(int u,int v)
{
    int t1,t2;
    t1=getf(u);
    t2=getf(v);
    if(t1!=t2)
    {
        f[t2]=t1;
    }
}
///////////////////////////////////////
int main()
{
    init();
    char s1[20],s2[20];
    cnt=0;
    while(scanf("%s %s",s1,s2)!=EOF)
    {
        int u,v;
        if(searchh(s1)==0)
        {insertt(s1);
        d[searchh(s1)]++;
        u=searchh(s1);}
        else
        {d[searchh(s1)]++;
        u=searchh(s1);}
        if(searchh(s2)==0)
        {insertt(s2);
        d[searchh(s2)]++;
        v=searchh(s2);}
        else
        {d[searchh(s2)]++;
        v=searchh(s2);}
        int fu=getf(u);
        int fv=getf(v);
        if(fu!=f[v])
        {sett(fu,fv);}
    }
    int op=0;
    for(int i=1;i<=cnt;i++)
    {
        int u=getf(i);
        if(i==u)
        {op++;}
    }
    if(op==0)
    {printf("Possible\n");}
    else if(op!=1)
    {printf("Impossible\n");}
    else
    {
        int odd=0;
        for(int i=1;i<=cnt;i++)
        {
            if(d[i]%2==1)
            {odd++;}
        }
        if(odd!=2&&odd!=0)
        {printf("Impossible\n");}
        else
        {printf("Possible\n");}
    }
    return 0;
}

123