T1:欧拉路径

Description

18世纪著名的数学问题之一:在哥尼斯堡的一个公园里,有7座桥将河中两个岛及河两岸连接起来(如图a)。问是否可能从这四块陆地中任一块出发,恰好通过每座桥一次,再回到起点?   

欧拉于1736年研究并解决了此问题。欧拉把每一块陆地考虑成一个点,连接两块陆地的桥以边表示,画出图b的图论模型,由此问题变成:能否从无向图的一个结点出发走出一条路径,每条边恰好经过一次,最后回到出发点。这样的路线称为欧拉回路,也可以称为一笔画。

你的任务与欧拉一样:给出n个顶点(编号为1..n),m条边的无向图。请寻找一条欧拉路径。

Input

第1行为整数n,接下来的 m 行,每行两个整数:i,j(1<=i,j<=n),表示一条无向边。

Output

如果不存在欧拉路径,则输出NIE。否则输出应当包含 m+1 个整数,依次表示欧拉路径经过的顶点号。如果把欧拉路径经过的结点序列看成是一个n进制的数,那么当存在多组解的情况下,输出n进制表示法中最小的一个(也就是输出第一个数较小的,如果还有多解,输出第二个数较小的,…,实质就是字典序)。

Sample Input

1
2
3
4
5
6
7
8
9
10
7 9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6

Sample Output

1
1 2 3 4 2 5 4 6 5 7

Sample Input 图示:(欧拉路为 1 2 3 4 2 5 4 6 5 7

Hint

1<=n<=500, 1<=m<=1024

分析

一道欧拉路径的模板题,大致思路和求解欧拉路的模板算法一样,只是这个题要求输出字典序最小的欧拉路经上的点,那么可以想到将边集数组改变,因为原本的前向星不能保证字典序最小

可以用 Vector 模拟边集数组,进行排序之后再 DFS ,就可以保证求得欧拉路的时候字典序最小了,这可能会丢失修改 head 数组的时间优化,但是这个题数据太水,也能 AC

Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define maxn 501
#define maxm 1025
using namespace std;
struct edge{
int id,to;
bool operator <(const edge &obj)const{
return to<obj.to;
}
}; vector<edge> g[maxn];
bool vis[maxm*2]; int res[2*maxm];
int f[maxn];
int n,m,deg[maxn];
inline int Sfind(int x){
if(f[x]==x) return x;
else return f[x]=Sfind(f[x]);
}
void dfs_euler(int u){
vector<edge>::iterator iter=g[u].begin();
while(iter!=g[u].end()){
if(!vis[iter->id]){
vis[iter->id]=true;
dfs_euler(iter->to);
}
iter++;
}
res[++res[0]]=u;
} int cnt;
int main(){
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
freopen("testout.txt","w",stdout);
#endif
cin>>n>>m; int U,V,fu,fv;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++){
cin>>U>>V;
g[U].push_back((edge){i,V});
g[V].push_back((edge){i,U});
deg[U]++; deg[V]++;
fu=Sfind(U); fv=Sfind(V);
f[fu]=fv;
}
for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
int st=1;
// JUDGE 1
for(int i=1;i<=n;i++)
if(deg[i]&1) cnt++;
if(cnt>2){
cout<<"NIE"; return 0;
}
// JUDGE 2
for(int i=2;i<=n;i++)
if(Sfind(f[i])!=Sfind(f[i-1])){
cout<<"NIE"; return 0;
}
for(int i=1;i<=n;i++)
if(deg[i]&1){st=i;break;}
dfs_euler(st);
for(int i=res[0];i>=1;i--) cout<<res[i]<<' ';
return 0;
}

T2:欧拉回路

Description

有一天一位灵魂画师画了一张图,现在要你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。

一共两个子任务:

  1. 这张图是无向图。(50分)
  2. 这张图是有向图。(50分)

Input

第一行一个整数 t

第二行两个整数 n,m

接下来 m行,每行两个整数u,v

如果 t=1 表示无向边(u,v),如果 t=2 表示有向边,图中可能有重边也可能有自环。

Output

如果不可以一笔画,输出一行 “NO”。

否则,输出一行 “YES”,接下来一行输出一组方案。

如果 t=1,输出m个整数:p1,p2…m。表示边的编号。若pi为正,表示从ui走到vi,否则表示从vi走到ui如果 t=2,输出m个整数,表示边的编号。

Sample Input #1

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

Sample Output #1

1
2
YES
3 -2 -1

Sample Input #2

1
2
3
4
5
6
7
8
2
5 6
2 3
2 5
3 4
1 2
4 2
5 1

Sample Output #2

1
2
YES
4 1 3 5 2 6

Sample Input #2 图示:(欧拉路为 4,1,3,5,2,6

Hint

1≤n≤10^5,0≤m≤2×10^5

分析

求解欧拉路径的一个模板题,因为 m 的范围不大,可以用比较好写的 DFS 来求解,大致思路和求解欧拉路径的模板代码一样,这里说说如何存放欧拉路上的边的编号

对于y

由于无向图加边的连续性,如果边集数组的 tot 从 1 开始,那么对于一对点 (u,v) 来说,从 u 到 v 的边号始终是奇数(1,3,5,7,……),从 v 到 u 的反向边就是偶数,由此就可以判断当前边的方向,然后看是存正编号还是负编号

对于无向图,在判断某条边是否访问过时,把无向图想成有向图,那么每条边的编号将会缩小一倍(除以 2),这样走过之后把 $vis[i\div 2]$ 标记即可,判断也只判断 $vis[i\div 2]$ ,加边时也要加 $i\div 2$

对于有向图,直接对这条边的编号进行操作即可

Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#define maxn 100001
#define maxm 5*100001
// for not directed graph
using namespace std;
int head[maxn],nxt[maxm],to[maxm];
int res[maxm],tot=1,n,m;
int ind[maxn],oud[maxn]; // outdegs and indegs
bool vis[2*maxn]; int typ;
inline void Eadd(int u,int v){
nxt[++tot]=head[u]; to[tot]=v;
head[u]=tot;
}
void euler(int u){
for(int &i=head[u];i;i=nxt[i]){
int v=to[i]; int c=(typ==1)?(i/2):(i-1);
int s=i%2;
if(vis[c]) continue;
vis[c]=true;
euler(v);
if(typ==1) res[++res[0]]=(s?(-c):c);
else res[++res[0]]=c;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
freopen("testout.txt","w",stdout);
#endif
cin>>typ;
cin>>n>>m; int x,y;
for(int i=1;i<=m;i++){
cin>>x>>y; Eadd(x,y);
if(typ==1) Eadd(y,x);
oud[x]++; ind[y]++;
}
// JUDGE
if(typ==2){
for(int i=1;i<=n;i++)
if(ind[i]!=oud[i]){
cout<<"NO";
return 0;
}
}else{
for(int i=1;i<=n;i++)
if((ind[i]+oud[i])&1){
cout<<"NO";
return 0;
}
}
// SOLVE
for(int i=1;i<=n;i++)
if(head[i]){
euler(i);break;
}
if(res[0]!=m) { cout<<"NO"; return 0;}
cout<<"YES\n";
for(int i=res[0];i;i--) cout<<res[i]<<' ';
return 0;
}