Catenyms

题目大意

定义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<cstdio>
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>

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> 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<edge[u].size();i++) {
        if(!edge[u][i].vis) {
            edge[u][i].vis = true;
//            cout<<edge[u][i].letter<<'-';        
            
            dfs(edge[u][i].to);
            ans[cnt++] = edge[u][i].id;  // 这行是得到答案的关键，逆序存储字典序最小的路径
        }
    }
}

int main()
{
    int T, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);

        init();
        int st = 26;
        for(int i=1;i<=n;i++) {
            char s[25];
            scanf("%s", s);
            letters[i] = s;
        }
        
        sort(letters+1, letters+1+n);

        for(int i=1;i<=n;i++) {
            int u = letters[i][0] - 'a';
            int v = *(letters[i].end()-1) - 'a';
            edge[u].push_back(Edge(v, i));
            out[u]++;
            in[v]++;
            st = min(st, u);
        }

        int num = 0;
        bool can = true;
        for(int i=0;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) {
            printf("***
");
            continue;
        }
//        cout<<st<<endl;
        dfs(st);
        if(cnt!=n) {
            printf("***
");
            continue;
        }
        
        for(int i=cnt-1;i>=0;i--) {
            printf("%s%c", letters[ans[i]].c_str(), i!=0?'.':'
');
        }

    }
    return 0;
}

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

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstring>
#include<algorithm>
using namespace std;
// 来源：https://www.cnblogs.com/wd-one/p/4539305.html

int 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
", edge[step[1]].c);
        }
        else
            printf("***
");
    }
    return 0;
}

View Code

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

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstring>
#include<algorithm>
using namespace std;
// 参考自 https://www.cnblogs.com/wd-one/p/4539305.html
int 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("***
");
            } else {
                for(int i = n; i>=1; i--)  {
                    printf("%s%c", edge[step[i]].c, i==1?'
':'.');
                }
            }
            
        } else {
            printf("***
");
        }
    }
    return 0;
}

View Code

（完）