欧拉路 / 回路 / 有向/ 无向 / 字典顺序

/**
    欧拉路就是一笔画问题，同时会衍生出好多问题
    比如：单词接龙，就是给一堆英文单词，问是否能让其首尾相接
    排成一列
    这样可将每个单词看成一条边，首尾字母看成点，求是否存在一
    条欧拉路

    一、无向图
    欧拉回路：每个顶点入度都是偶数
    欧拉路：所有点度数为偶数或者只有两个点度数为奇数
    二、有向图
    欧拉回路：每个点入度等于出度
    欧拉路：每个点入度等于出度或只有一个点入度比出度小1（从这个
    点出发），只有一个点出度比入度小1（从这个点结束），其它点
    入度等于出度。

    例子：按字典顺序输出有向图的欧拉路

    struct node {
        int u, v;
        int vis;  //是否访问过，初始为0
        int w;    //边权,w可以使任意类型，当然也可以使字符串
    }edge[eM];    //存边

    int n, m;     //表示点的个数，边得个数

    int in[nM], out[nM], root[nM], path[nM];
    //入度，出度，并查集用，记录路径

    //初始化，除root,其余都赋值为零
    for (int i=0; i<=n; i++)
        root[i] = i;   //root 初始化，并查集用

    //添边操作
    int k = 0; //k的个数最后赋给m
    void addEdge(int u, int v, int w) {
        edge[k].u = u;
        edge[k].v = v;
        edge[k++].w = w;
        in[v]++;        //入度
        out[u]++;       //出度
        //下面时并查用，判断图联通
        int x = find(u);
        int y = find(v);
        if (x != y)
            root[x] = y;
    }

    //find 函数,并查集经常用的，这个题主要判断图联通，
    int find(int x) {
        return root[x] == x ? : root[x] = find(root[x]);
    }

    //现在判断是否存在欧拉路，这里以欧拉路为例，其它都比较简单

    int start = judge();    //定义一个起点
    //judge() 函数
    int judge() {
        int num=0, ns=0, ne=0, s=-1;
        for (int i=1; i<=n; i++) {
            if (find(i) == i)   num++;  //根节点个数
            if (in[i] != out[i]) {
                if (in[i]-out[i] == 1)
                    ne++;   //  结束点，入度比出度大一
                else if (out[i]-in[i] == 1) {
                    ns++;
                    s = i;  // 起始点
                }
                else
                    return -1;  //返回 -1 代表不存在
            }
        }
        if (num != 1)   return -1;
        if (!((ns==1&&ne==1) || (ns==0&&ne==0)))
            return -1;   //不符合存在欧拉路的条件
        if (s == -1)     //如果s == -1 则随便返回一个起点
            return 1;    //这里返回 1
        return s;
    }

    //如果start == -1 则不存在欧拉路
    //如需按字典输出，则对边按权值优先排序
    sort();

    //递归输出欧拉路
    k = 0;
    eular(start);
    //eular() 函数
    void eular(int u) {
        for (int i=0; i<m; i++) {
            if (!edge[i].vis && edge[i]==u) {
            //无向图条件 (edge[i].u==u || edge[i].v==u)
                edge[i].vis = true;
                eular(edge[i].v);
            //无向图的话 eular(edge[i].v+edge[i].u - u);
                path[k++] = i;
            }
        }
    }

    //从 k-1 -> 0 输出路径

    欧拉路判断最为复杂，其它三种尤其无向图，judge() 函数
    比较容易写，这就不写了，根据上面它所对应的规则

    图算法都不在于本身，而在于把问题转换成图算法

    只要经过足够的练习，都是浮云，这个比赛考智商么，那些牛人
    之所以能很快把题做出来，只有一个可能，这个题型他以前见过，
    大量练习才是王道。

    POJ 2337 1041
*/

//这几天在看新版福尔摩斯，超级精彩  http://tv.sohu.com/20110218/n279411831.shtml

收藏于 2012-01-18
来自于百度空间