一笔画问题.docx
《一笔画问题.docx》由会员分享，可在线阅读，更多相关《一笔画问题.docx（14页珍藏版）》请在冰点文库上搜索。
一笔画问题
2014-7-15一笔画问题简单学习总结
今天学的还是图论的内容——一笔画问题。
一笔画就是把一个无向图（或有向图）所有的边都遍历一遍且不重复走同样的边。
这个新知识的算法都是建立在几个数学性质上面的,分别如下:
1、这个有向图（或无向图）必须是连通的。
这是最基本的条件。
2、每个点之间度的要求:
无向图:
满足①所有点的度数为偶数或者②有两个点度数为奇数,其他点度数为偶数,且这两个奇数点必须为一笔画中的开端和结尾。
有向图:
满足①所有点出入度相等或者②有一个点出度比入度大1,另一个点入度比出度大1,其他点的出入度相等,且出度大的点为一笔画开端,入度大的点为一笔画结尾。
数学简单证明还是比较容易的,如果一个点度数为奇数,那么从该点出发,去到的无非就两种情况:
偶点或奇点,偶点我们总可以绕一个圈回到该偶点重新出发。
奇点就到达终点了。
（圈套圈的思路）
对于无向边,有一个特殊处理:
无向边路过一条边后,要把它的反向边去掉。
这个过程可以用指针实现,用一个指针指向它的反向边。
或者,如果用数组来储存边时,因为反向边是同时申请的,所以它们的下标一定是相邻的,可以用异或操作得到。
下面介绍几种算法:
1、圈套圈算法
算法思想:
每次在某个点随便找一条边,一直走,如果找到环,那么就相应地插入到一笔画的顺序中,环中若有嵌套环,那么同样地找下去。
算法实现:
可以用链表实现插入之类的操作,但若用深搜回溯写的话,程序会非常简单。
就是从奇点（或任意点）出发,任意地深度遍历,如果当前点已经不能往下搜,那么就回溯看祖先节点是否有其他可以遍历的点,按回溯的顺序弹出的边,在无向图里面正反顺序都是一笔画正确解法,有向图里需要取反顺序。
算法优化:
由于系统栈的空间局限性,在朴素的递归算法里面不能支持较大数据范围的题目,可以改成用stack栈模拟递归的操作,这样就不再会爆栈。
2、弗罗莱算法
算法思想:
首先在奇点出发,尽量先不走桥（若去掉该边图不连通,则该边为桥）,先走环路。
只要顺序地走一遍就是一笔画解法。
算法实现:
判断一边是否为桥的方法是按照定义,去掉改边后,用宽度搜索遍历一遍。
如何判断一个图是否能实现一笔画?
根据上述一笔画所需的条件性质,我们可以做一次BFS判断该图是否连通。
值得注意的是,当一些点如A、B未在读入出现过时,一切操作和判断应该略过这些点,因为这些点根本没有在图中。
同时,判断奇数点是否只有两个或者没有,否则不能实现一笔画。
做了三道练习题,题目的变形比较小,但还是有许多值得注意的细节。
第一题《多米诺》
题目大意:
给出一些多米诺骨牌（1*2的方块）,左右面都有一个0~6的数字。
你可以任意调整这些骨牌的相对顺序,还可以旋转它们,要求使得这些骨牌数字首尾相连（类似于单词接龙）
题目分析:
首先建一个图,图的点最多有7个（0~6）,根据多米诺骨牌上的内容在两个数字之间建边,由于可以旋转,所以这边应该是无向边。
构图完毕后,便是求一笔画问题的顺序。
最后输出摆放和旋转情况即可（任一解即可）（可能无解）
这个程序写得不是很好,模块化程度不够,链接矩阵使用较随意,链表写得复杂,最后输出边的编号时效率太低。
需要改正。
程序如下:
#include
#include
#include
usingnamespacestd;
structNode
{
Node*nex;
intnp;
Node（）{nex=NULL;np=0;}
};
Nodespace[1024];
intn,iSpace=0;
intcnt[7];
Node*hea[10],*tai[10];
intans[1024],m=0;
intadj[10][10];
intgpa[102],gpb[102];
Node*getNew（）{return&space[iSpace++];}
voidpushback（inta,intb）
{
if（tai[a]==NULL）
{
tai[a]=hea[a]=getNew（）;
tai[a]->np=b;
}
else
Node*A=getNew（）;
A->np=b;
tai[a]->nex=A;
tai[a]=A;
}
}
voidwork（intst）;
queueq;
boolvis[7];
boolused[102];
boolcheck（ints）
{
q.push（s）;
vis[s]=true;
while（!
q.empty（））
{
intnow=q.front（）;
q.pop（）;
for（Node*i=hea[now];i!
=NULL;i=i->nex）
{
intNex=i->np;
if（!
vis[Nex]）
{
q.push（Nex）;
vis[Nex]=true;
}
}
}
for（inti=0;i<=6;++i）if（cnt[i]!
=0&&vis[i]==false）returnfalse;
returntrue;
}
intmain（）
{
memset（cnt,0,sizeof（cnt））;
memset（adj,0,sizeof（adj））;
cin>>n;
ints=1;
for（inti=1;i<=n;++i）
inta,b;
cin>>a>>b;
gpa[i]=a;gpb[i]=b;
cnt[a]++;cnt[b]++;
pushback（a,b）;
pushback（b,a）;
adj[a][b]++;adj[b][a]++;
s=a;
}
intst=s,len=0;
for（inti=0;i<=6;++i）
if（cnt[i]%2==1）
{
st=i;
len++;
}
if（len==1||len>2||!
check（s））cout<<"Nosolution"<else
{
work（st）;
for（inti=1;i<=m;i+=2）
{
inta=ans[i];
intb=ans[i+1];
for（intj=1;j<=n;++j）
{
if（used[j]==true）continue;
if（gpa[j]==a&&gpb[j]==b）
{
cout<used[j]=true;
break;
}
elseif（gpa[j]==b&&gpb[j]==a）{
cout<used[j]=true;
break;
}
}
}
}
system（"pause"）;
return0;
}
voidwork（intst）
{
for（Node*i=hea[st];i!
=NULL;i=i->nex）
{
intj=i->np;
if（adj[st][j]==0）continue;
adj[st][j]--;adj[j][st]--;
work（j）;
ans[++m]=st;
}
ans[++m]=st;
}
第二题《单词接龙》
题目大意:
给你一些单词,让你首尾串起来串成一串,并且输出一个字典序最小的方案。
题目分析:
和上面的多米诺骨牌一样,区别在于单词不能旋转,所以构图要改为有向边,相应地,判断时就要区分出入度的区别。
字典序最小,我们可以通过给链接链表的边排序,这样访问时就会优先搜索到字典序小的边。
除此之外,我们在确定起点时,除了奇点的情况,偶点必须找到字典序最小的点作为起点。
程序如下:
采用非递归的栈模拟写法,模块程度较高。
#include
#include
#include
#include
#include
#include
#include
usingnamespacestd;
constintmaxn=1024;
structEdge
{
intnex;
intedgP;
Edge（）{nex=edgP=0;}
Edge（inta,intb）{nex=a;edgP=b;}};
stringwords[maxn];
intn;
intind[30],outd[30];
queueq;
boolvis[30];
vectoredg[30];
vectorans;
stackpoint,edge;
voidinit（）;
boolcmp（Edgea,Edgeb）;
boolbfs（）;
intcheck（）;
voidStack_DFS（intst）;
voidprint_ans（）;
intmain（）
{
//freopen（"B.in","r",stdin）;
intT;
cin>>T;
for（inti=0;i!
=T;++i）
{
init（）;
intst=check（）;
if（st==-1）cout<<"***"<else
{
Stack_DFS（st）;
print_ans（）;
}
}
system（"pause"）;
return0;
}
boolcmp（Edgea,Edgeb）
{
returnwords[a.edgP]}
voidinit（）
{
memset（ind,0,sizeof（ind））;
memset（outd,0,sizeof（outd））;
for（inti=1;i<=26;++i）edg[i].clear（）;
cin>>n;
for（inti=0;i!
=n;++i）
{
stringst;
cin>>st;
words[i]=st;
inta=int（st[0]）-96;
intb=int（st[st.size（）-1]）-96;
outd[a]++;ind[b]++;
edg[a].push_back（Edge（b,i））;
}
for（inti=1;i<=26;++i）
sort（edg[i].begin（）,edg[i].end（）,cmp）;
}
boolbfs（intst）
{
memset（vis,false,sizeof（vis））;
q.push（st）;
vis[st]=true;
while（!
q.empty（））
{
intnow=q.front（）;
q.pop（）;
for（inti=0;i!
=edg[now].size（）;++i）
{
intNex=edg[now][i].nex;
if（!
vis[Nex]）
{
q.push（Nex）;
vis[Nex]=true;
}
}
}
for（inti=1;i<=26;++i）
if（（ind[i]!
=0||outd[i]!
=0）&&vis[i]==false）return
false;
returntrue;
}
intcheck（）
{
intlen=0,st=-1;
for（inti=1;i<=26;++i）
{
if（ind[i]-outd[i]>1||outd[i]-ind[i]>1）return-1;
if（ind[i]!
=outd[i]）
{
len++;
if（outd[i]>ind[i]）st=i;
}
elseif（ind[i]!
=0&&st==-1）st=i;
}
if（len==1||len>2||!
bfs（st））return-1;
returnst;
}
intadj[30];
voidStack_DFS（intst）
{
ans.clear（）;
memset（adj,0,sizeof（adj））;
point.push（st）;
edge.push（-1）;
while（!
point.empty（））
{
intx=point.top（）;
if（adj[x]==edg[x].size（））
{
point.pop（）;
ans.push_back（edge.top（））;
edge.pop（）;
continue;
}
intp=adj[x];
inty=edg[x][p].nex;
intz=edg[x][p].edgP;
adj[x]++;
point.push（y）;
edge.push（z）;
}
}
voidprint_ans（）
{
for（inti=ans.size（）-2;i>=0;--i）
{
if（i!
=0）cout<elsecout<}
cout<}
第三题《单词接龙简化》
题目大意:
题目中给你n个字符串,问你能不能找到一种排列方案,使前一个单词的尾部字符是下一个单词的首部字母。
题目分析:
由于只需要判断是否能达成一笔画问题,而不需要打印方案,我们的DFS程序可以省去,只需要做出入度的判断和图是否连通的操作即可。
由于是多组数据,程序的初始化非常重要,建议把所有改动过的数据统一初始化,免得漏掉出错。
程序如下:
#include
#include
#include
#include
usingnamespacestd;
structNode
{
Node*nex;
intnp;
};
Nodespace[802000];
intn,iSpace=0;
charstr[1024];
stringstr1;
intcntr[30],cnto[30];
Node*hea[30],*tai[30];
Node*getNew（）{return&space[iSpace++];}
voidpushback（inta,intb）
{
if（tai[a]==NULL）
{
hea[a]=tai[a]=getNew（）;
tai[a]->np=b;
}
else
{
Node*A=getNew（）;
A->np=b;
tai[a]->nex=A;
tai[a]=A;
}
}
queueq;
intvis[31];
boolcheck（intst）
{
memset（vis,0,sizeof（vis））;
q.push（st）;
vis[st]=true;
while（!
q.empty（））
{
intnow=q.front（）;
q.pop（）;
for（Node*i=hea[now];i!
=NULL;i=i->nex）
{
intNex=i->np;
if（!
vis[Nex]）
{
q.push（Nex）;
vis[Nex]=true;
}
}
}
for（inti=1;i<=26;++i）if（cntr[i]!
=0&&vis[i]==false）returnfalse;
returntrue;
}
intmain（）
{
freopen（"c.in","r",stdin）;
intT;
scanf（"%d",&T）;
intst;
for（inti=0;i!
=T;++i）
{
//iSpace=0;
memset（cntr,0,sizeof（cntr））;
memset（cnto,0,sizeof（cnto））;
for（intj=0;j<=29;++j）hea[j]=tai[j]=NULL;
scanf（"%d",&n）;
for（intj=1;j<=n;++j）
{
scanf（"%s",str）;
str1=str;
inta=int（str[0]）-96;
intb=int（str[str1.size（）-1]）-96;
cnto[a]++;cntr[b]++;
pushback（a,b）;
//pushback（b,a）;
st=a;
}
intlen=0;
for（inti=1;i<=26;++i）
{
if（cntr[i]!
=cnto[i]）
{
if（cnto[i]>cntr[i]）st=i;
len++;
}
if（cntr[i]-cnto[i]>1||cnto[i]-cntr[i]>1）
len+=10;
}
if（len==1||len>2||!
check（st））printf（"Thedoorcannotbeopened.\n"）;
elseprintf（"Orderingispossible.\n"）;
}
system（"pause"）;
return0;
}
升级会员 