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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注