test

6.11集训队选拔赛有道欧拉图的题,没带模板就尝试去写没写出来。因为在acm里欧拉图的题可以说是少之又少,就算是我现在想要去复习一编,然而连题目都找不到几个。就算有欧拉图的题目,也只是考察他的性质(欧拉图的判定啊什么的)

阅读之前请读者自备图论相关常识

Fleury算法是一种解决欧拉图的常见算法,它的核心思想在于我在进欧拉路径的时候,尽量去走非桥边。其实这是很显然的,因为当你在走过了一个桥边,原图将被分为两个子图,如果之前还有边未走完,那么我将无法回到原子图上,也就无法形成欧拉路径了。

优先走非桥边,这是一个非常必要的前提条件,而事实证明,这也是一个充分条件。
以下是我整理的个人模板

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 110;

int stk[maxn], ans[maxn], degree[maxn];
int top, atop;
int n, m, st, num;
bool go[maxn][maxn];

void dfs(int u)
{
    stk[top++] = u;
    for (int i = 1; i <= n; ++i) {
        if (go[u][i]) {
            go[u][i] = go[i][u] = 0;
            degree[i]--;
            degree[u]--;
            dfs(i);
            break;
        }
    }
}

void fleury(int st)
{
    top = atop = 0;
    stk[top++] = st;
    while (top > 0) {
        if (degree[stk[top - 1]])
            dfs(stk[--top]);
        else
            ans[atop++] = stk[--top]; //bridge
    }
    while (atop > 1)
        printf("%d ", ans[--atop]);
    printf("%d\n", ans[0]);
}

inline void init()
{
    memset(go, false, sizeof go);
    memset(degree, 0, sizeof degree);
    st = num = 0;
}

int main()
{
    int u, v;
    while (scanf("%d %d", &n, &m) != EOF) {
        init();
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            go[u][v] = go[v][u] = true;
            degree[u]++;
            degree[v]++;
        }
        for (int i = 1; i <= n; i++)
            if (degree[i] & 1) {
                num++;
                st = st ? st : i;
            }
        if (num == 0)
            fleury(1);
        else if (num == 2)
            fleury(st);
        else
            puts("No Euler Path!");
    }
    return 0;
}
Categories: 欧拉图

发表评论

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

Related Posts

欧拉图

51Nod 1967 路径定向

首先说一下这道题的思路真的是非常巧妙。 但是,出题人脑子进shi了么, Read more…

同余BFS

HDU 6071 Lazy Running

第一次刷到HDU第一名,趁现在没人比我高,截图来一发!!!! 对于这道 Read more…

BEST THEOREM

BEST THEOREM ( 附 HDU 6064

昨晚多校的以为是数论的图论题,我看许学姐也是忙得不可开交肯定是没去看过 Read more…