有向图的欧拉路径POJ2337

时间：2021-01-12 10:40:17

每个单词可以看做一条边，每个字母就是顶点。

有向图欧拉回路的判定，首先判断入度和出度，其实这个题判定的是欧拉通路，不一定非得构成环，所以可以有一个点的顶点入度比出度大1，另外一个点的出度比入度大1，或者每个点的出度和入度相等。用并查集判断是否弱联通。最后dfs求出欧拉路径，不过这个题是让求字典序最小的那个，所以加边之前先把边排序。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

using namespace std;

const int maxn = ;

struct Edge {

    int to, next;

    int id;

}edge[maxn * ];

int tot, head[maxn];

int in[maxn], out[maxn];

int F[maxn];

int st;

bool vis[];

string str[maxn];

void init()

{

    tot = ;

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

    memset(F, -, sizeof(F));

}

void addedge(int u, int v, int id)

{

    edge[tot].to = v;

    edge[tot].next = head[u];

    edge[tot].id = id;

    head[u] = tot++;

}

int Find(int x)

{

    if (F[x] == -) return x;

    return F[x] = Find(F[x]);

}

void Union(int x, int y)

{

    int tx = Find(x);

    int ty = Find(y);

    if (tx != ty)

        F[tx] = ty;

}

bool check(int s)

{

    int in1 = , out1 = ;

    for (int i = ; i <= ; i++)//判断出入度关系

    {

        if (in[i] == out[i]) continue;

        else if (in[i] - out[i] == ) in1++;

        else if (out[i] - in[i] == ) out1++, st = i;//如果有出度比入度大1的，说明是欧拉通路，起点只能是那个出度比入度大1的那个点

        else return false;

    }

    //printf("in1 = %d, out1 = %d\n", in1, out1);

    if (!(in1 ==  && out1 == ) && !(in1 ==  && out1 == )) return false;

    for (int i = ; i <= ; i++)//判断弱联通

        if (vis[i] && Find(i) != Find(s))

            return false;

    return true;

}

bool vis2[maxn * ];//判断每条边是否访问过。

int top;

int ans[maxn * ];//保存路径

void dfs(int u)

{

    for (int i = head[u]; i != -; i = edge[i].next)

    {

        if (!vis2[i])

        {

            vis2[i] = true;

            dfs(edge[i].to);

            ans[top++] = i;

        }

    }

}

int main()

{

    int T, n;

    scanf("%d", &T);

    while (T--)

    {

        init();

        scanf("%d", &n);

        memset(in, , sizeof(in));

        memset(out, , sizeof(out));

        memset(vis, false, sizeof(vis));

        int u, v;

        st = ;

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

            cin >> str[i];

        sort(str, str + n);//从小到大排序

        for (int i = n - ; i >= ; i--)//因为链式前向星是逆序存图，所以反过来从大到小读入。

        {

            u = str[i][] - 'a' + ;

            v = str[i][str[i].length() - ] - 'a' + ;

            vis[u] = vis[v] = true;

            addedge(u, v, i);

            ++in[v];

            ++out[u];

            Union(u, v);

            st = min(st, min(u, v));//找出最小的那个点来

        }

        if (!check(st))

            puts("***");

        else

        {

            top = ;

            memset(vis2, false, sizeof(vis2));

            dfs(st);

            for (int i = top - ; i > ; i--)

                cout << str[edge[ans[i]].id] << ".";

            cout << str[edge[ans[]].id] << endl;

        }

    }

    return ;

}

相关文章