题意:
给一个无向图..请输出一条从1出发..每条边经过两次最终落到1的路径(经过点的顺序..数据保证存在至少一条路径)...输出任意一条符合要求的....
题解:
把每条无向边拆成两个有向边<u,v>,<v,u>...那么题目就变成了从1点出发的欧拉回路..输出遍历点的顺序..方法在usaco上有详细的说明here就是从一个点进去以后..将它所有的边都扩完了..再输出自己..也可以先压到栈里面去.最后倒过来输出...
Program:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<time.h>
#include<map>
#include<algorithm>
#define ll long long
#define eps 1e-5
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 10005
#define MAXM 100005
using namespace std;
struct node
{
int y,next;
}line[MAXM];
int Lnum,_next[MAXN],ans[MAXN],num;
bool used[MAXM];
void addline(int x,int y)
{
line[++Lnum].next=_next[x],_next[x]=Lnum,line[Lnum].y=y;
}
void dfs(int x)
{
for (int k=_next[x];k;k=line[k].next)
if (!used[k])
{
used[k]=true;
dfs(line[k].y);
}
printf("%d\n",x);
}
int main()
{
int n,m,x,y;
scanf("%d%d",&n,&m);
Lnum=0,memset(_next,0,sizeof(_next));
while (m--)
{
scanf("%d%d",&x,&y);
addline(x,y),addline(y,x);
}
num=0,memset(used,false,sizeof(used));
dfs(1);
return 0;
}