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[];

string letters[];

int in[], out[];     // 顶点的入度与出度

int ans[], cnt;

void init() {

    cnt = ;

    memset(in, , sizeof(in));

    memset(out, , sizeof(out));

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

        edge[i].clear();

    }

}

void dfs(char u) {

    for(int i=;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 = ;

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

            char s[];

            scanf("%s", s);

            letters[i] = s;

        }

        sort(letters+, letters++n);

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

            int u = letters[i][] - 'a';

            int v = *(letters[i].end()-) - 'a';

            edge[u].push_back(Edge(v, i));

            out[u]++;

            in[v]++;

            st = min(st, u);

        }

        int num = ;

        bool can = true;

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

            if(out[i]-in[i]==) {

                ++num;

                if(num==) {

                    st = i;

                } else {

                    can = false;

                    break;

                }

            } else if(out[i]-in[i]> || in[i]-out[i]>) {

                can = false;

                break;

            }

        }

        if(!can) {

            printf("***\n");

            continue;

        }

//        cout<<st<<endl;

        dfs(st);

        if(cnt!=n) {

            printf("***\n");

            continue;

        }

        for(int i=cnt-;i>=;i--) {

            printf("%s%c", letters[ans[i]].c_str(), i!=?'.':'\n');

        }

    }

    return ;

}

参考别人没有建图的代码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[], in[], step[], pre[];

int n, k, t, st;

char w[];

struct Edge//结构体：边， 存储了边的起点（首字符）和终点（尾字符），状态（是否走过）

{

    int s, e, v;

    char c[];

}edge[];

bool cmp(Edge x, Edge y)

{

    return strcmp(x.c, y.c) <  ? true : false;

}

int find(int x)//查找其父节点

{

    if(pre[x] != x)

        pre[x] = find(pre[x]);

    return pre[x];

}

int panduan()//判断是否图是连通的

{

    int fx = find(edge[].s);

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

    {

        if(out[i] >  || in[i] > )

        {

            if(find(i) != fx)

                return ;

        }

    }

    return ;

}

void path(int en)//查找路径

{

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

    {

        if(edge[i].v ==  && edge[i].s == en)

        {

            edge[i].v = ;

            path(edge[i].e);

            step[++k] = i;

        }

    }

}

int main()

{

    cin >> t;

    while(t--)

    {

        memset(out, , sizeof(out));

        memset(in, , sizeof(in));

        memset(step, , sizeof(step));

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

            pre[i] = i;

        scanf("%d", &n);

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

        {

            cin >> w;

            int len = strlen(w);

            int s = w[] - 'a' + ;

            int e = w[len - ] - 'a' + ;

            edge[i].s = s;

            edge[i].e = e;

            strcpy(edge[i].c, w);

            edge[i].v = ;

            out[s]++;

            in[e]++;

            /*如果存在欧拉路径，那么所有的点一定都连通.所有的点都在一个集合里，可以用并查集知识

            将所有连接的点并到一起。*/

            int fx = find(s);

            int fy = find(e);

            if(fx != fy)

                pre[fx] = fy;

        }

        sort(edge + , edge +  + n, cmp);//题目要求字典序最小输出，就先按从小到大的顺序把边（单词）排好

        /*st代表的是路径起点，在这里进行st = edge[1].s赋值，是应为存在两种情况：1.存在一定点出度>入度,

        这个点是起点。2.所有点出度= 入度， 那么从任意一点出发都可以， 为了保证字典序最小， 就从第一个单词开始*/

        st = edge[].s;

        int i, c1 = , c2 = ;

        for(i = ; i <= ; i++)//判断是否有欧拉回路

        {

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

            else if(in[i] == out[i] - ) {c1++; st = i;}//起点

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

            else break;

        }

        //如果符合了连通图，并且存在欧拉通路， 就开始找路径

        if(i ==  && ((c1 == c2 && c1 == ) || (c1 == c2 && c1 == )) && panduan() == )

        {

            k = ;

            path(st);

            for(int i = n; i > ; i--)//输出这注意点，因为是递归求的路径， 最先得到的是最后的边

                printf("%s.", edge[step[i]].c);

            printf("%s\n", edge[step[]].c);

        }

        else

            printf("***\n");

    }

    return ;

}

上面的代码并查集部分似乎不太必要，大概能加快连通图的判断，修改成自己的风格后依旧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[], in[], step[];

int n, k, st;

struct Edge

{

    int s, e, vis;

    char c[];

}edge[];

bool cmp(const Edge &x, const Edge &y)

{

    return strcmp(x.c, y.c) < ;

}

void path(int st)

{

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

    {

        if(edge[i].vis ==  && edge[i].s == st)

        {

            edge[i].vis = ;

            path(edge[i].e);

            step[++k] = i;

        }

    }

}

int main()

{

    int t; cin >> t;

    while(t--)

    {

        memset(out, , sizeof(out));

        memset(in, , sizeof(in));

        memset(step, , sizeof(step));

        scanf("%d", &n);

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

        {

            char w[];

            scanf("%s", w);

            int len = strlen(w);

            int s = w[] - 'a' + ;

            int e = w[len - ] - 'a' + ;

            edge[i].s = s;

            edge[i].e = e;

            strcpy(edge[i].c, w);

            edge[i].vis = ;

            out[s]++;

            in[e]++;

        }

        sort(edge + , edge +  + n, cmp);

        st = edge[].s;

        int num = ;

        bool can = true;

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

            if(out[i]-in[i]==) {

                ++num;

                if(num==) {

                    st = i;

                } else {

                    can = false;

                    break;

                }

            } else if(out[i]-in[i]> || in[i]-out[i]>) {

                can = false;

                break;

            }

        }

        if(can)

        {

            k = ;

            path(st);

            if(k!=n)  {

                printf("***\n");

            } else {

                for(int i = n; i>=; i--)  {

                    printf("%s%c", edge[step[i]].c, i==?'\n':'.');

                }

            }

        } else {

            printf("***\n");

        }

    }

    return ;

}

（完）

巴特西

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

Catenyms

题目大意

数据范围

题目解答

最新文章

热门文章