Catenyms
Time Limit:1000MSMemory Limit:65536K
Total Submissions:10427Accepted:2726
Description
A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the last letter of the second. For example, the following are catenyms:dog.gophergopher.ratrat.tigeraloha.alohaarachnid.dogA compound catenym is a sequence of three or more words separated by periods such that each adjacent pair of words forms a catenym. For example,aloha.aloha.arachnid.dog.gopher.rat.tigerGiven a dictionary of lower case words, you are to find a compound catenym that contains each of the words exactly once.
Input
The first line of standard input contains t, the number of test cases. Each test case begins with 3 <= n <= 1000 – the number of words in the dictionary. n distinct dictionary words follow; each word is a string of between 1 and 20 lowercase letters on a line by itself.
Output
For each test case, output a line giving the lexicographically least compound catenym that contains each dictionary word exactly once. Output "***" if there is no solution.
Sample Input
26alohaarachniddoggopherrattiger3oakmapleelm
Sample Output
aloha.arachnid.dog.gopher.rat.tiger***
出度。
欧拉路是欧拉回路的一种情况。
有向图存在欧拉路的充要条件为：
① 图是连通的；
② ，或者除两个结点外（一个节点的出 = 入度 + 1，，一个节点的入度 = 出度 + 1），其余每个结点的入度=出度。
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;int head[30], cnt;struct node {int u ,v, id, next; // 纪录边的编号bool flag;//标记这条别是否用过。};node edge[2020];int ans;string str[1010];int path[1010];//纪录路径；int in[30], out[30];void init(){cnt = 0;memset(head, -1, sizeof(head));memset(in, 0, sizeof(in));memset(out, 0, sizeof(out));}void add(int u ,int v, int id){edge[cnt] = {u, v, id, head[u]};head[u] = cnt++;}void dfs(int u){for(int i = head[u]; i != -1; i = edge[i].next){if(!edge[i].flag){edge[i].flag = true;dfs(edge[i].v);path[ans++] = edge[i].id;}}}int main (){int T, n;scanf("%d", &T);while(T–){scanf("%d", &n);for(int i = 0 ; i < n ;++i)cin >> str[i];sort(str, str + n);init();int st = 1000;for(int i = n – 1; i >= 0; i–){int len = str[i].length();int u = str[i][0] – 'a';int v = str[i][len – 1] – 'a';add(u, v, i);in[v]++, out[u]++;st = min(st, u);st = min(st, v);//纪录字典序最小的点作为起点，对应欧拉回路出现的这种情况}int numst, numed, num;numst = numed = num = 0;for(int i = 0 ; i < 26; ++i){if(!in[i] && !out[i]) continue;if(in[i] != out[i]) num++;if(out[i] – in[i] == 1){//如果有一个出度比入度大1的点，就从这个点出发，否则从最小的点出发numst++;st = i;}else if(out[i] – in[i] == -1)numed++;}if(num > 0){if(!(num ==2 && numst == 1 && numed == 1)){//不是欧拉路也不是欧拉回路；cout <<"***"<<endl;continue;}}ans = 0;dfs(st);if(ans != n){ //不连通,注意这种判连通的方式cout <<"***"<<endl;continue;}for(int i = ans – 1; i >= 0; –i){cout<<str[path[i]];if(i > 0)printf(".");elseprintf("\n");}}return 0;}
在有向图中，判断是不是欧拉路的代码
int numst, numed, num;numst = numed = num = 0;for(int i = 0 ; i < 26; ++i){if(!in[i] && !out[i]) continue;if(in[i] != out[i]) num++;if(out[i] – in[i] == 1){//如果有一个出度比入度大1的点，就从这个点出发，否则从最小的点出发numst++;st = i;}else if(out[i] – in[i] == -1)numed++;}if(num > 0){if(!(num ==2 && numst == 1 && numed == 1)){cout <<"***"<<endl;continue;}}
在网上看到另一种判断有向图存在欧拉路的代码，可以参考一下
int cc1 = 0, cc2 = 0;for(int i = 0;i < 26;i++){if(out[i] – in[i] == 1){cc1++;st = i;//如果有一个出度比入度大1的点，就从这个点出发，否则从最小的点出发}else if(out[i] – in[i] == -1)cc2++;else if(out[i] – in[i] != 0)cc1 = -1;}if(! ( (cc1 == 0 && cc2 == 0) || (cc1 == 1 && cc2 == 1) )){printf("***\n");continue;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
每一发奋美文努力的背后，必有加倍的赏赐。
