【学习笔记】欧拉路&哈密顿路

发表于 
1
2
3
4
5
6
7
8
9
10
```
<!--more-->
欧拉路：
 - 1.存在性判断：
     无向图：无奇点等价于欧拉回路；有两个奇点等价于欧拉通路
     有向图：所有点的入度都等于出度等价于存在欧拉回路；一个点入度比出度多1，另一个点出度比入度多1等价于欧拉通路
     
 - 2.fleury算法：
DFS(u):
    While (u存在未被删除的边e(u,v))
        删除边e(u,v)
        DFS(v)
    End
    PathSize ← PathSize + 1
    Path[ PathSize ] ← u

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    注意有向图的欧拉路要倒序输出
    
    
[很好的资料](http://www.cnblogs.com/TheRoadToTheGold/p/8439160.html)
哈密顿路（np问题）：
- 1.狄拉克定理：如果图G是一个具有$n(n\geq 3)$个顶点的简单无向图，并且图G中每个顶点的度数至少为$n/2$，那么图G是哈密顿图（具有哈密顿回路的图）。（证明：归纳）
    奥勒定理（dirac定理的推广）：如果图G是一个具有$n(n\geq 3)$个顶点的简单无向图，并且图G中每一对不相邻的顶点u和v满足$deg(u)+deg(v)\geq n$，那么图G是哈密顿图。
    
- 2.n(n>=2)阶竞赛图一定存在哈密顿通路。（证明：归纳）
  当且仅当竞赛图是强连通的，存在哈密顿回路。（证明：归纳）
  
- 3.竞赛图上的哈密顿回路
    先找到一个环，再在环上扩展。
    hdu3414


#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
#include<queue>
#include<bitset>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=1008;
int n;
int a[N][N];
int nxt[N];
bool vis[N];
bool flag;
int cnt;

inline bool dfs(int x)
{
    vis[x]=1;
    if(a[x][1]){
        nxt[x]=1;
        ++cnt;
        return 1;
    }
    for(int i=2;i<=n;++i){
        if(!vis[i]&&a[x][i]){
            if(dfs(i)){
                nxt[x]=i;
                ++cnt;
                return 1;
            }
        }
    }
    return 0;
}
inline void solve()
{
    memset(nxt,0,sizeof(nxt));
    memset(vis,0,sizeof(vis));
    cnt=0;
    if(!dfs(1)){
        puts("-1");
        return;
    }

    while(1){
        flag=0;
        for(int i=2;i<=n;++i){
            if(!nxt[i]){
                for(int j=1;j<=n;++j){
                    if(nxt[j]&&a[j][i]&&a[i][nxt[j]]){
                        nxt[i]=nxt[j];
                        nxt[j]=i;
                        ++cnt;
                        flag=1;
                        break;
                    }
                }
            }
        }

        if(!flag){
            break;
        }
    }
    if(cnt==n){
        printf("1");
        for(int i=nxt[1];i!=1;i=nxt[i]){
            printf(" %d",i);
        }
        puts("");
    }
    else{
        puts("-1");
    }
}
int main()
{
    while(1){
        scanf("%d",&n);
        if(!n)    return 0;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                a[i][j]=read();
            }
        }
        if(n==1){
            puts("1");
            continue;
        }
        solve();
    }
    return 0;
}
```