Catenyms (POJ2337) 字典序最小欧拉路-白红宇

Catenyms (POJ2337) 字典序最小欧拉路

阅读量：4992 次

发布时间：2019-06-12

本文共 6456 字，大约阅读时间需要 21 分钟。

// 很久不写图论，连模板也不熟悉了0.0

// 这题是一个技巧性比较高的暴力DFS

题目大意

定义catenym为首尾字母相同的单词组成的单词对，例如：

dog.gopher
gopher.rat
rat.tiger
aloha.aloha
arachnid.dog

而catenym系统则是多个利用该规则组成的单词串，例如：

aloha.aloha.arachnid.dog.gopher.rat.tiger

给定一组单词，让你判断是否能组成catenym系统，且每个单词只能使用一次。

无解时输出“***”。

数据范围

单词长度 1~20，单词个数 3 <= n <= 1000

题目解答

图论专场的练习题，一看要输出所有单词的序列，感觉就是拓扑排序。

于是想当然地把每个单词作为顶点，能首尾相连的关系作为边。如果能得到这个图的拓扑排序（每个单词都刚好用上了），并且保持字典序，那么刚好就是本问题的解。

问题在于，拓扑排序必须是有向无环图（DAG），而单词之间的边关系很容易就成环了，这个方法就行不通了O.O

经过队友指点，发现可以把26个字母当作顶点，单词作为边，题意也就是要找到一条通过所有边的路径，即求解字典序最小的欧拉路！！！

来复习一下离散数学的知识：

1.无向连通图 G 是欧拉图，当且仅当 G 不含奇数度结点( G 的所有结点度数为偶数)；

2.无向连通图 G 含有欧拉通路，当且仅当 G 有零个或两个奇数度的结点；

3.有向连通图 D 是欧拉图，当且仅当该图为连通图且 D 中每个结点的入度=出度；

4.有向连通图 D 含有欧拉通路，当且仅当该图为连通图且 D 中除两个结点外，其余每个结点的入度=出度。

所以怎么获得欧拉路呢？

需要首先判断是否是欧拉图（具有欧拉回路）或半欧拉图（具有欧拉通路）：只需要记录每个点的出度和入度，根据（半）欧拉图相关定理判定即可。

dfs判断连通性

逆序输出dfs序列（建图时按字典序排序后加入边）

一开始直接看了题解也是一头雾水，最终形成了自己理解的算法。采用邻接表的写法：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;struct Edge { int to; int id; // 边的编号 letters[id] = letter bool vis; // dfs是否访问过// string letter; Edge(int v, int i): to(v), id(i) { vis = false; }};vector
            
              edge[30];string letters[1010];int in[30], out[30]; // 顶点的入度与出度int ans[1010], cnt;void init() { cnt = 0; memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); for(int i=0;i<26;i++) { edge[i].clear(); }}void dfs(char u) { for(int i=0;i
             
              1 || in[i]-out[i]>1) { can = false; break; } } if(!can) { printf("***\n"); continue; }// cout<
              
               <
               
                =0;i--) { printf("%s%c", letters[ans[i]].c_str(), i!=0?'.':'\n'); } } return 0;}

参考别人没有建图的代码0ms，采用并查集缩点，判断是否联通：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;// 来源：https://www.cnblogs.com/wd-one/p/4539305.htmlint out[30], in[30], step[1005], pre[30];int n, k, t, st;char w[25];struct Edge//结构体：边， 存储了边的起点（首字符）和终点（尾字符），状态（是否走过）{    int s, e, v;    char c[25];}edge[1005];bool cmp(Edge x, Edge y){    return strcmp(x.c, y.c) < 0 ? true : false;}int find(int x)//查找其父节点{    if(pre[x] != x)        pre[x] = find(pre[x]);    return pre[x];}int panduan()//判断是否图是连通的{    int fx = find(edge[1].s);    for(int i = 1; i <= 26; i++)    {        if(out[i] > 0 || in[i] > 0)        {            if(find(i) != fx)                return 0;        }    }    return 1;}void path(int en)//查找路径{    for(int i = 1; i <= n; i++)    {        if(edge[i].v == 0 && edge[i].s == en)        {            edge[i].v = 1;            path(edge[i].e);            step[++k] = i;        }    }}int main(){    cin >> t;    while(t--)    {        memset(out, 0, sizeof(out));        memset(in, 0, sizeof(in));        memset(step, 0, sizeof(step));        for(int i = 1; i <= 30; i++)            pre[i] = i;        scanf("%d", &n);        for(int i = 1; i <= n; i++)        {            cin >> w;            int len = strlen(w);            int s = w[0] - 'a' + 1;            int e = w[len - 1] - 'a' + 1;            edge[i].s = s;            edge[i].e = e;            strcpy(edge[i].c, w);            edge[i].v = 0;            out[s]++;            in[e]++;            /*如果存在欧拉路径，那么所有的点一定都连通.所有的点都在一个集合里，可以用并查集知识            将所有连接的点并到一起。*/            int fx = find(s);            int fy = find(e);            if(fx != fy)                pre[fx] = fy;        }        sort(edge + 1, edge + 1 + n, cmp);//题目要求字典序最小输出，就先按从小到大的顺序把边（单词）排好        /*st代表的是路径起点，在这里进行st = edge[1].s赋值，是应为存在两种情况：1.存在一定点出度>入度,        这个点是起点。2.所有点出度= 入度， 那么从任意一点出发都可以， 为了保证字典序最小， 就从第一个单词开始*/        st = edge[1].s;        int i, c1 = 0, c2 = 0;        for(i = 1; i <= 26; i++)//判断是否有欧拉回路        {            if(out[i] == in[i])continue;            else if(in[i] == out[i] - 1) {c1++; st = i;}//起点            else if(in[i] == out[i] + 1) c2++;            else break;        }        //如果符合了连通图，并且存在欧拉通路， 就开始找路径        if(i == 27 && ((c1 == c2 && c1 == 1) || (c1 == c2 && c1 == 0)) && panduan() == 1)        {            k = 0;            path(st);            for(int i = n; i > 1; i--)//输出这注意点，因为是递归求的路径， 最先得到的是最后的边                printf("%s.", edge[step[i]].c);            printf("%s\n", edge[step[1]].c);        }        else            printf("***\n");    }    return 0;}

View Code

上面的代码并查集部分似乎不太必要，大概能加快连通图的判断，修改成自己的风格后依旧0ms：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;// 参考自 https://www.cnblogs.com/wd-one/p/4539305.htmlint out[30], in[30], step[1005];int n, k, st;struct Edge{    int s, e, vis;    char c[30];}edge[1005];bool cmp(const Edge &x, const Edge &y){    return strcmp(x.c, y.c) < 0;}void path(int st){    for(int i = 1; i <= n; i++)    {        if(edge[i].vis == 0 && edge[i].s == st)        {            edge[i].vis = 1;            path(edge[i].e);            step[++k] = i;        }    }}int main(){    int t; cin >> t;    while(t--)    {        memset(out, 0, sizeof(out));        memset(in, 0, sizeof(in));        memset(step, 0, sizeof(step));          scanf("%d", &n);        for(int i = 1; i <= n; i++)        {            char w[25];            scanf("%s", w);            int len = strlen(w);            int s = w[0] - 'a' + 1;            int e = w[len - 1] - 'a' + 1;            edge[i].s = s;            edge[i].e = e;            strcpy(edge[i].c, w);            edge[i].vis = 0;            out[s]++;            in[e]++;        }        sort(edge + 1, edge + 1 + n, cmp);          st = edge[1].s;        int num = 0;        bool can = true;        for(int i=1;i<=26;i++) {            if(out[i]-in[i]==1) {                ++num;                if(num==1) {                    st = i;                } else {                    can = false;                    break;                }            } else if(out[i]-in[i]>1 || in[i]-out[i]>1) {                can = false;                break;            }        }               if(can)        {            k = 0;            path(st);             if(k!=n)  {                printf("***\n");            } else {                for(int i = n; i>=1; i--)  {                    printf("%s%c", edge[step[i]].c, i==1?'\n':'.');                }            }                    } else {            printf("***\n");        }    }    return 0;}

View Code

（完）

转载于:https://www.cnblogs.com/izcat/p/11148880.html

你可能感兴趣的文章