POJ 2230 Watchcow「欧拉回路」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/181

原题地址:点击打开链接

这题终于是纯粹的欧拉回路了……关于欧拉回路,各位可以看一下我写的这篇博客:欧拉回路

如果你知道怎么做欧拉回路,那么这题就很简单了,使用邻接表建立邻接关系,这题中的所有边都是有向边,而且两个顶点之间的边是成对出现的,所以所有的顶点度必定是偶数,必定存在欧拉回路。使用递归查找欧拉回路,并且在递归函数的最后一句可以打印当前的节点,这样子打印的结果和当前查找的顺序是相反的,但是没有关系——因为本题的边是成对出现的,反着走肯定也是可以走得通的。

从某一个点开始寻找回路,必定会以当前这个点结束,為什麼呢?参考我上面写的博客吧。里面也已经说完了这道题目应该说的东西了。

直接贴出代码如下:

#include<iostream>
#include<memory.h>
#include<stdio.h>
#include<vector>
#define MAXN 10005
using namespace std;
int n,m,tmp;
vector<int> edge[MAXN];
void euler(int index)
{
    for(int i=0;i<edge[index].size();i++)
    {
      tmp=edge[index][i];
      if(tmp==-1)
        continue;
      edge[index][i]=-1;
      euler(tmp);
    }
    printf("%d\n",index);
}
int main()
{
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    scanf("%d%d",&n,&m);
    int tmpa,tmpb;
    for(int i=0;i<m;++i)
    {
      scanf("%d%d",&tmpa,&tmpb);
      edge[tmpa].push_back(tmpb);
      edge[tmpb].push_back(tmpa);
    }
    euler(1);
}

 

发表评论

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