图论-欧拉回路（邻接链表）

Watchcow

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 7633		Accepted: 3342		Special Judge

Description

Bessie's been appointed the new watch-cow for the farm. Every night, it's her job to walk across the farm and make sure that no evildoers are doing any evil. She begins at the barn, makes her patrol, and then returns to the barn when she's done. 

If she were a more observant cow, she might be able to just walk each of M (1 <= M <= 50,000) bidirectional trails numbered 1..M between N (2 <= N <= 10,000) fields numbered 1..N on the farm once and be confident that she's seen everything she needs to see. But since she isn't, she wants to make sure she walks down each trail exactly twice. It's also important that her two trips along each trail be in opposite directions, so that she doesn't miss the same thing twice. 

A pair of fields might be connected by more than one trail. Find a path that Bessie can follow which will meet her requirements. Such a path is guaranteed to exist.

Input

* Line 1: Two integers, N and M. 

* Lines 2..M+1: Two integers denoting a pair of fields connected by a path.

Output

* Lines 1..2M+1: A list of fields she passes through, one per line, beginning and ending with the barn at field 1. If more than one solution is possible, output any solution.

Sample Input

4 5
1 2
1 4
2 3
2 4
3 4

Sample Output

1
2
3
4
2
1
4
3
2
4
1

Hint

OUTPUT DETAILS: 

Bessie starts at 1 (barn), goes to 2, then 3, etc...

Source

USACO 2005 January Silver

 

 

 

题意：

　　Bessie 最近做了农场看守，他每天晚上的工作就是巡视农场并且保证没有坏人破坏农场。从谷仓出发去巡视，并且最终回到谷仓。

　　Bessie 视力不是很好，不能像其他农场的看守一样，对农场的每一条连接不同场地的路走一遍就可以发现是不是有异常情况，他需要每条路都走两遍，并且这两边必须是不同的方向，因为他觉得自己应该不会两次都忽略农场中的异常情况。

　　每块地之间一定会由至少一条路相连。现在的任务就是帮他制定巡视路线。前提假设一定存在满足题意的路径。

输入：

　　第一行输入两个数N(2 <= N <= 10000)和M(1 <= M <= 50000)，表示农场一共有N块地M条路。

　　第二到M+1行输入两个整数，表示对应的两块地之间有一条路。

输出：

　　输出2 * (m + 1)行，每行一个数字，表示Bessie 的巡查路径上地的编号，1号为谷仓，从1开始，从1结束。如果有多种答案，输出任意一种。

样例输入

4 5

1 2

1 4

2 3

2 4

3 4

样例输出

1

2

3

4

2

1

4

3

2

4

1

---

从两个方向走，是一个无向图，也相当于有两条往返的道路

一定有欧拉回路

注意！！！！

数组要开双倍

#include<iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int m,n;
struct side{                    //邻接链表储存 ，储存边 
    int next;
    int to;
}e[100005];                        //注意！！！双向图，每条边储存两次，so。。。。。数组要开两倍     
int s=0;
int h[20005];                    //记录某顶点的第一条边 
void in(int u,int v){
    s++;                    //边数增加 
    e[s].to =v;                //该边指向 
    e[s].next =h[u];        //将边插入到链表前端，next就是原来u顶点的第一条边 
    h[u]=s;                    //现在u顶点第一条边是s 
    s++;                    //无向图，往返都可以 
    e[s].to =u;
    e[s].next =h[v];
    h[v]=s;
}
bool vis[100005];            //判重 
void dfs(int u){
    for(int i=h[u];i;i=e[i].next ){                //欧拉回路要求经过每一条边，即一笔画 
        if(vis[i]==1)continue;                    //故遍历u顶点的每一条边 
        vis[i]=1;
        dfs(e[i].to );                            //遍历该边指向的顶点        
    }
    cout<<u<<"
";                                //该顶点走完，输出 
}
int main(){
    cin>>n>>m;
    int u,v;
    for(int i=0;i<m;i++){
        cin>>u>>v;
        in(u,v);
    }
    dfs(1); 
    return 0;
}