POJ2337 欧拉路径字典序输出

题意：

给一些单词，问是否可以每个单词只用一次，然后连接在一起（不一定要成环，能连接在一起就行）。

思路：

这个题目的入手点比较好想，其实就是问欧拉路径，先说下解题步骤，然后在细说

（1）把每个单词看成一条边，单词的首字母和尾字母是点

（2）然后记录入度，出度，根据入度出度判断是不是欧拉路径或者回路

（3）别往了判断所有点是不是属于同一个连通子集，这个可以用并查集啥的

（4）把所有的边都排序下，至于是什么顺序，根据自己的存图方式去排

（5）欧拉路径就从头开始（要是欧拉回路就找个最小的点）深搜找出路径

之前也没写过输出欧拉路径啥的啊！看有人说可以用栈递归存边，然后就在纸上画了几个8想想，觉得有道理，就自己写了一个欧拉路的(其实很简单)，至于排序的地方，我想的是直接在存边之前先把边排序下，因为欧拉路径输出的时候也是比较简单“画6的感觉”，要求字典序最小，因为我用的是前向星，其实这个东西建边是倒叙的，就是a-b a-c a-d 的顺序进去，那么访问的时候是a-d,a-c,a-b这样的，全都是抱着试一试，结果直接a了。虽然是简单题，但是挺高兴啊。

#include<stack>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define N_node 30

#define N_edge 1000 + 100

using namespace std;

typedef struct

{

    int to ,next;

}STAR;

typedef struct

{

    char str[30];

}EDGE;

STAR E[N_edge];

EDGE edge[N_edge];

int list[N_node] ,tot;

int mer[N_node];

int mark[N_edge];

int deg[N_node];

stack<int>mysk;

bool camp(EDGE a ,EDGE b)

{

    return strcmp(a.str ,b.str) > 0;

}

void add(int a ,int b)

{

    E[++tot].to = b;

    E[tot].next = list[a];

    list[a] = tot;

}

int finds(int x)

{

    return x == mer[x] ? x : mer[x] = finds(mer[x]);

}

void DFS(int s)

{

    for(int k = list[s] ;k ;k = E[k].next)

    {

        if(mark[k]) continue;

        mark[k] = 1;

        DFS(E[k].to);

        mysk.push(k);

    }

}

int main ()

{

    int t ,n ,i ,j;

    int mkc[30];

    scanf("%d" ,&t);

    while(t--)

    {

        scanf("%d" ,&n);

        memset(deg ,0 ,sizeof(deg));

        memset(mkc ,0 ,sizeof(mkc));

        for(i = 1 ;i <= 26 ;i ++)

        mer[i] = i;

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

        {

            scanf("%s" ,edge[i].str);

            int a = edge[i].str[0] - 'a' + 1;

            int b = edge[i].str[strlen(edge[i].str)-1] - 'a' + 1;

            mer[finds(a)] = finds(b);

            mkc[a] = mkc[b] = 1;

            deg[a] ++;

            deg[b] --;

        }

        int s = 0 ,z = 0 ,f = 0 ,min;

        for(i = 1 ;i <= 26 ;i ++)

        {

            if(mkc[i])

            {

                if(mer[i] == i) s ++;

                if(!deg[i]) continue;

                if(deg[i] == 1)

                z ++ ,min = i;

                else if(deg[i] == -1) f ++;

                else s ++;

            }

        }

        if(s != 1 || f + z != 0 && f + z != 2)

        {

            printf("***\n");

            continue;

        }

        sort(edge + 1 ,edge + n + 1 ,camp);

        memset(list ,0 ,sizeof(list));

        tot = 1;

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

        {

            int a = edge[i].str[0] - 'a' + 1;

            int b = edge[i].str[strlen(edge[i].str)-1] - 'a' + 1;

            add(a ,b);

        }

        if(z + f == 0) min = edge[n].str[0] - 'a' + 1;

        while(!mysk.empty())

        mysk.pop();

        memset(mark ,0 ,sizeof(mark));

        DFS(min);

        while(!mysk.empty())

        {

            int tou = mysk.top();

            mysk.pop();

            if(mysk.empty())

            printf("%s\n" ,edge[tou-1].str);

            else printf("%s." ,edge[tou-1].str);

        }

    }

    return 0;

}

巴特西

POJ2337 欧拉路径字典序输出

最新文章

热门文章