CCF-CSP题解 201512-4 送货

求字典序最小欧拉路。

似乎不能用\(Fluery\)算法（\(O(E^2)\)）。\(Fluery\)算法的思路是：延申的边尽可能不是除去已走过边的图的桥（割）。每走一步都要判断是否是割，应当会超时。

采用\(Hierholzer\)算法（\(O(V+E)\)），亦称逐步插入回路法。思路见代码。注意根据题意，每次选取未走过顶点最小的边延申。

注意题目要求从1号节点出发。

欧拉路存在的条件：

无向图：

存在欧拉回路的条件：原图连通，每个节点均为偶度节点。

存在欧拉通路的条件：存在欧拉回路，或原图连通，有两个节点为奇度节点，其他节点均为偶度节点。

有向图：

存在欧拉回路的条件：基图（有向边变成无向边）连通，每个节点的入度等于出度。

存在欧拉通路的条件：存在欧拉回路，或基图连通，有一个节点入度等于出度+1，有一个节点出度等于入度+1，其他节点入度等于出度。

#include<bits/stdc++.h>

const int maxn = 10000;

const int maxm = 100000;

using namespace std;

int to[maxm * 2 + 10];

int vis[maxm * 2 + 10];

int nex[maxm * 2 + 10];

int head[maxn + 10], cnt = 0;

void addEdge(int a, int b)

{

    to[cnt] = b;

    vis[cnt] = 0;

    nex[cnt] = head[a];

    head[a] = cnt++;

    to[cnt] = a;

    vis[cnt] = 0;

    nex[cnt] = head[b];

    head[b] = cnt++;

}

int degree[maxn + 10];

int vis1[maxn + 10], num = 0;

void dfs(int x)

{

    vis1[x] = 1;

    num++;

    for (int i = head[x]; i != -1; i = nex[i])

    {

        int l = to[i];

        if (!vis1[l])

            dfs(l);

    }

}

int main()

{

    int n, m;

    scanf("%d%d", &n, &m);

    memset(head, -1, sizeof(head));

    memset(degree, 0, sizeof(degree));

    for (int i = 1, a, b; i <= m; i++)

    {

        scanf("%d%d", &a, &b);

        addEdge(a, b);

        degree[a]++;

        degree[b]++;

    }

    memset(vis1, 0, sizeof(vis1));

    dfs(1);

    int odd = 0;

    for (int i = 1; i <= n; i++)

    {

        if (degree[i] % 2)

            odd++;

    }

    if (num == n && (odd == 0 || (odd == 2 && degree[1] % 2)))

    {

        stack<int> s1, s2;

        s1.push(1);

        while (!s1.empty())

        {

            int x = s1.top();

            int y = -1, ii = -1;

            for (int i = head[x]; i != -1; i = nex[i])

            {

                if (vis[i])

                    continue;

                int l = to[i];

                if (y == -1 || y > l)

                    y = l, ii = i;

            }

            if (y == -1)

            {

                s2.push(x);

                s1.pop();

            }

            else

            {

                vis[ii] = vis[ii ^ 1] = 1;

                s1.push(y);

            }

        }

        bool first = true;

        while (!s2.empty())

        {

            if (first)

            {

                printf("%d", s2.top());

                s2.pop();

                first = false;

            }

            else

            {

                printf(" %d", s2.top());

                s2.pop();

            }

        }

        printf("\n");

    }

    else

    {

        printf("-1\n");

    }

    return 0;

}

巴特西

CCF-CSP题解 201512-4 送货

最新文章

热门文章