欧拉路径&欧拉回路
判定
无向图
- 欧拉路径：可以一笔画，充要条件是度数为奇数的点的个数为0或2
- 欧拉回路：欧拉路劲构成一个环，充要条件是全部是偶点
有向图
- 欧拉路径：起点出度比入度大1，终点入度比出度大1，其他全部是偶点
- 欧拉回路：每个点出入度相同（至多存在两个点出入度不同，且这两个点满足起点出度比入度大1，终点入度比出度大1），且存在一系列环可以覆盖原图
求路径：Fleury算法
求图的欧拉回路的算法：Fleury算法
对于无向图和有向图，求路径的方法是一样的，简单描述为：在任意可行点处进行dfs，过程中找到一条回路之后从终点开始往回删除dfs过程中的所有边（注意，这里如果是无向图的话，需要删双向边，那么可以通过异或操作完成）如果删掉这些边之后的点还能够通往别的路径的话，就继续dfs通往，直到递归结束，此时，倒着输出所有遍历的节点就行了（无向图正着倒着都一样），以上过程都可以通过dfs的特性（栈）一气呵成
伪代码
| void dfs(int u){
for(遍历所有u的出边){
if(出边没被删){
删掉这条边（无向图需要删双向，可以用^运算实现）
dfs(这条边所连的点)
}
}
把u压入栈中
}
|
具体代码见下方例题2、3
模板题
判断一个无向图是否有欧拉路径
code
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
| #include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> gg[50005];
int main(){
cin>>n>>m;
int u,v;
for(int i=1;i<=m;i++){
cin>>u>>v;
gg[u].push_back(v);
gg[v].push_back(u);
}
int ans=0;
for(int i=1;i<=n;i++){
int temp=0;
int Size=gg[i].size();
for(int i=0;i<Size;i++){
temp++;
}
if(temp%2!=0){
ans++;
}
}
if(ans==0||ans==2) cout<<"Full"<<endl;
else cout<<"Part"<<endl;
return 0;
}
|
重题POJ 2230 Watchcow（但此题用stack会RE）
求一个无向图的任意一条欧拉回路
应用Fleury算法，代码如下
code
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
| #include<bits/stdc++.h>
using namespace std;
int n,m;
struct Edge{
int u,v,w,next;
bool f;
}e[50005];
int cnt,head[50005];
void init(){
memset(head,-1,sizeof(head));
cnt=0;
}
inline void addedge(int u,int v,int w=0){
e[cnt]=Edge{u,v,w,head[u],false};
head[u]=cnt++;
}
stack<int> sta;
void dfs(int u){
for(int i=head[u];~i;i=e[i].next){
int v=e[i].v;
if(!e[i].f){
e[i].f=e[i^1].f=1;
dfs(v);
}
}
sta.push(u);
}
int main(){
cin>>n>>m;
int u,v;init();
for(int i=1;i<=m;i++){
cin>>u>>v;
addedge(u,v);
addedge(v,u);
}
dfs(1);
while(sta.size()){
cout<<sta.top()<<" ";
sta.pop();
}
return 0;
}
|
题意：
给出一个正整数n，求一个长度为$2^n$的01环，使得该环的每n位恰好构成$0~2^{n-1}$，例如：n=3时，答案为00010111
题解：
很有意思的一道题，考虑将其转化为图论题：例如，对于n=3的情况，抽取其中任意的长度为3的子串，如：101，将其拆分为10、01，那么就可以建图从(10)->(01)，由此，从$0~2^{n-1}-1$只要有一个数的后n-1位和另一个数的前n-1位相同，那么就可以从前一个数连一条边到后一个数，显然共有$2^n$条边，跑一次欧拉回路，用栈记录路径，最后输出时一定要倒着输出（栈&1）的值
AC代码：
code
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
| #include<bits/stdc++.h>
using namespace std;
int n,m;
struct Edge{
int u,v,w,next;
bool f;
}e[50005];
int cnt,head[50005];
void init(){
memset(head,-1,sizeof(head));
cnt=0;
}
inline void addedge(int u,int v,int w=0){
e[cnt]=Edge{u,v,w,head[u],false};
head[u]=cnt++;
}
stack<int> sta;
void dfs(int u){
for(int i=head[u];~i;i=e[i].next){
int v=e[i].v;
if(!e[i].f){
e[i].f=1;
dfs(v);
}
}
sta.push(u);
}
int main(){
cin>>n;
if(n==1){
cout<<"01"<<endl;
return 0;
}
init();
int k=(1<<n-2)-1;
for(int i=0;i<1<<n-1;i++){
int giao=i&k;
for(int j=0;j<1<<n-1;j++){
if(giao==j>>1){
addedge(i,j);
}
}
}
dfs(0);
sta.pop();
while(sta.size()){
cout<<(sta.top()&1);
sta.pop();
}
return 0;
}
|