【算法】欧拉路&欧拉回路

欧拉路和欧拉回路是数学家欧拉在研究七桥问题的时候提出的,其具体历史这里就不多说了。
简单区分下欧拉回路和欧拉路
欧拉路就是说所有的边走且只走一次,欧拉回路就是在欧拉路的基础上更进一层,不仅所有的边都走一次,最后还回到了起点
其实就是我们熟知的一笔画呗
这个算法其实比较结论。对于有向图和无向图我们只需要找准条件随便写一下就行了,混合图……反正我是没看懂23333333
有向图存在欧拉路:所有顶点出度等于入度(且存在欧拉回路);或者是出两点外,所有点出度等于入度,这两个点中,出度大的为起点,入度大的为终点。
无向图存在欧拉路:所有点度数均为偶数(且存在欧拉回路);或有两个奇数点,他们一定是终点和起点
代码实现的话直接dfs就好啦。反正是一笔画,所以只要能走就一直走就行,记住dfs的时候要修改边权
luogu P1341 无序字母对

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int n, dis[1010][1010], d[1010];

char s[1010], ans[1010], ss[1010];

void dfs(int no)
{
    for(ri i = 0; i < 52; i ++)
        if(dis[no][i])
            dis[no][i] = dis[i][no] = 0, dfs(i);
    ans[n --] = ss[no];
}

int main()
{
    re(n);
    for(ri i = 0; i < 26; i ++)
        ss[i] = 'A' + i;
    for(ri i = 26; i < 52; i ++)
        ss[i] = 'a' + i - 26;
    for(ri i = 1; i <= n; i ++)
    {
        scanf("%s", s + 1);
        int lx, ly;
        if(s[1] >= 'A' && s[1] <= 'Z')
            lx = s[1] - 'A';
        else
            lx = s[1] - 'a' + 26;
        if(s[2] >= 'A' && s[2] <= 'Z')
            ly = s[2] - 'A';
        else
            ly = s[2] - 'a' + 26;
        dis[lx][ly] = dis[ly][lx] = 1, d[lx] ++, d[ly] ++;
    }
    int num = 0, sta = -1;
    for(ri i = 0; i < 52; i ++)
        if(d[i] & 1)
        {
            num ++;
            sta = (sta == -1) ? i : sta;
        }   
    bool f = 0;
    if((num != 0 && num != 2) || f != 0)
    {
        printf("No Solution"); return 0;
    }
    if(sta == -1)
    {
        for(ri i = 0; i < 52; i ++)
            if(d[i] != 0)
            {
                sta = i; break;
            }
    }
    dfs(sta);
    if(n > 0)
    {
        printf("No Solution"); return 0;
    }
    printf("%s", ans);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注