欧拉路径/回路【luogu P1341】

Author Avatar
Axell 7月 26, 2019
  • 在其它设备中阅读本文章

传送门

#include <bits/stdc++.h>
using namespace std;

int n;
bool a[53][53],de[53];
char s[5];

int calc(char c){
    if (c>='a' && c<='z') return c-'a'+27;
    else return c-'A'+1;
}
char uncalc(int x){
    if (x>=1 && x<=26) return 'A'+x-1;
    else return 'a'+x-27;
}

stack <int> st;

void dfs(int x){
    for (int i=1;i<=52;++i){
        if (a[x][i]){
            a[x][i]=a[i][x]=0; //无向图不可反复走
            dfs(i);
            //如果要记录边,应在此处
        }
    }
    st.push(x);
}

int main(){
    cin>>n;
    int mt=52;
    for (int i=1;i<=n;++i){
        scanf("%s",s+1);
        int x=calc(s[1]),y=calc(s[2]);
        mt=min(mt,min(x,y));
        a[x][y]=a[y][x]=1;
        de[x]^=1,de[y]^=1;
    }
    vector <int> v;
    for (int i=1;i<=52;++i){
        if (de[i]&1){
            v.push_back(i);
        }
    }
    if (v.size()==0){
        dfs(mt);
    }else if (v.size()==2){
        dfs(v[0]);
    }else{
        puts("No Solution");
        return 0;
    }
    /**
     * 此处没有判图的连通性,一般是要判的,数据比较水
     */
    while (!st.empty()){
        printf("%c",uncalc(st.top()));
        st.pop();
    }
    return 0;
}

/**
 * 欧拉路问题
 * 定义:
 *      欧拉路径:从S-T存在一条路径,使得不重复地便历图中所有的边
 *      欧拉回路:上述定义中S=T的情况
 * 判定:
 *         首先图是连通图
 *         欧拉路径:无向图:有2个或0个点度数为奇;有向图:最多只能有两个点入度不等于出度,而且这两个点其中一个点的入度+1=出度,另一个点的出度+1=入度;
 *         欧拉回路:无向图:没有奇度数的点;有向图:所有顶点的入度等于出度;
 * 查找方案:
 *         如果有特殊点(奇度数;出度=入度+1),从该点开始;否则从任意一点开始
 *         注意路径上点和边的记录要到子节点dfs完后push,最后倒序输出
 */

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。

本文链接:https://axell.wind-flower.cn/archives/欧拉路径-回路【luogu-p1341】/