当前位置: 代码迷 >> 综合 >> poj 2230 Watchcow 欧拉回路
  详细解决方案

poj 2230 Watchcow 欧拉回路

热度:84   发布时间:2024-01-19 05:57:13.0

题意:

给一个图,求一种从点1出发,经过所有边恰好两次回到点1的方案,数据保证有解。

分析:

欧拉回路,改下次数就好了。

代码:

//poj 2230
//sep9
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxN=10024;
const int maxM=50048;
int head[maxN];
int used[maxM*2];
vector<int> path;
struct Edge
{int v,nxt;	
}edge[maxM*2];
int e,n,m;void dfs(int u)
{for(int i=head[u];i!=-1;i=edge[i].nxt){int cur=i|1;if(used[cur]<2){int v=edge[i].v;++used[cur];dfs(v);path.push_back(v);}}	
}int main()
{scanf("%d%d",&n,&m);int i;e=0;memset(head,-1,sizeof(head));memset(used,0,sizeof(used));path.clear();for(i=1;i<=m;++i){int u,v;scanf("%d%d",&u,&v);edge[e].v=v;edge[e].nxt=head[u];head[u]=e++;edge[e].v=u;edge[e].nxt=head[v];head[v]=e++;}dfs(1);reverse(path.begin(),path.end());printf("1\n");for(i=0;i<path.size();++i)printf("%d\n",path[i]);return 0;	
}