欧拉回路

欧拉回路

画一笔画时，整幅图一笔画成，线条之间可以交叉(两次通过同一个点)，但不会重复，也不会断掉，这就是欧拉路径
如果最后又回到起点，则称作欧拉回路。一个欧拉图可以有多个欧拉回路。

欧拉路，既可以在有向图上，也可以在无向图上，只是有向图对每条边经过的方向进行了限定。

条件

一幅图存在欧拉路的条件，也即这幅图可以用一笔画成的条件是

• 有向图，如果是弱连通的，且所有的顶点，入度等于出度，那么该图存在欧拉回路，这是充要条件
• 有向图，如果是弱连通的，且除开两个顶点，其他点得入度都等于出度，并且这两个顶点，一个入度比出度多1，另一个出度比入度少1，那么这个图虽然不存在欧拉回路，但是有欧拉路径，且是充要条件。
• 无向图，连通，且所有的顶点的度为偶数，存在欧拉回路的充要条件
• 无向图，连通，且除了两个顶点，其余顶点的度都是偶数，则虽然没有欧拉回路，但存在欧拉路径
• 无向图，连通，且可分为若干个，边不相交的环，则是欧拉图。

算法

深度优先，判断当前顶点出发的边是否已经访问，这样，dfs回溯的时候，当前顶点所有的边都已经遍历过了。

vis[边]而不是通常的vis[顶点]，按定义回路只访问边一次，点没有限制，还因为有可能有重边，自环的情况

模板：

Euler 模板：深搜，有重复的边、自环，所以要区分边，用边的编号，确保每边只访问一次，点不受限制


    dfs(int x){
        for each next 点: y{
            if(vis[边])
                continue;
            vis[边] = 1;
            dfs(y);
            path.push_back(边(x-y));
        }
    }
    实际输出的是 path的倒序

poj 1041

const int maxn = 1995;
const int maxm = 1000000;
vector< pair<int, int> > adj[maxn];
int vis[maxm];

int fa[maxn];

/*

前向星结构

*/

int head[man];
int to[maxm*2];
int link[maxm*2];
int index = 0;

void add_edge(int x, int y, int z){
    index++;

    to[index] = y;
    link[index] = head[x];
    head[x] = index;
}

#define CLR(x) memset((x), 0, sizeof((x)))


#define eid first
#define vtx second

void add(int x, int y, int z){

    adj[x].push_back(make_pair(z, y));
    adj[y].push_back(make_pair(z, x));
}

int get_fa(int x){

    return x == fa[x]?x:fa[x] = get_fa(fa[x]);
}
void dfs(int x, vector<int> &path){

    for(int i = 0; i < adj[x].size(); ++i){
        int e = adj[x][i].eid;
        int y = adj[x][i].vtx;
        if(vis[e])
            continue;
        vis[e] = 1;
        dfs(y, path);
        path.push_back(e); /*  在dfs后 */
    }
}
void init(){
        for(int i = 0; i < maxn; i++)
                adj[i].clear();
        memset(fa, 0, sizeof(fa));
        CLR(head);CLR(to);CLR(link);
        index = 0;
}
bool solve(vector<int> &path){

    /* 判断 连通性 */
    for(int i = 0; i < maxn; i++)
        fa[i] = i;
    for(int i = 0; i < maxn; i++){
        for(int j = 0; j < adj[i].size(); j++)
            fa[get_fa(i)] = get_fa(adj[i][j].vtx);

    }

    int origin = -1;
    for(int i = 1; i < maxn; i++){
        if(adj[i].empty())
            continue;
        if(adj[i].size()%2 == 1) return false;
        if(origin == -1)
                origin = i;
        if(get_fa(i) != get_fa(origin)) return false;

        sort(adj[i].begin(), adj[i].end());
    }

    if(origin == -1) return false;

    path.clear();
    memset(vis, 0, sizeof(vis));

    dfs(origin, path);
    reverse(path.begin(), path.end()); /*  逆序 */

    return true;
}

int main(){

    int x,y,z;
    while(scanf("%d%d", &x, &y)){
        if(x == 0 && y == 0)
            break;
        scanf("%d", &z);
        init();
        add(x, y, z);
        while(scanf("%d%d", &x, &y)){
            if(x == 0 && y == 0)
                break;
            scanf("%d", &z);
            add(x, y, z);
        }

        vector<int> path;

        if(!solve(path)){
            printf("Round trip does not exist.\n");
        }else{
            int i;
            for(i = 0; i < path.size()-1; i++)
                printf("%d ", path[i]);
            printf("%d\n", path[i]);
        }
    }


    return 0;
}

总结

• 以边为访问标记而不是顶点
• dfs只进行一次就可以，顶点对于欧拉回路可以随意选择
• path的添加在dfs回溯之后进行，每次添加的是无路可进的边，添加的顺序，是dfs最先访问完的边