原题链接: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