这道题昨天晚上开始做，今天才A。但是问题想透了， 发现其实没那么难
题目大意：
给你一些单词，如果一个单词的末尾字符与另一个单词首字符相同，则两个的单词可以连接。问是否可以把所有单词连接起来，并且每个单词只能用一次。
分析：
可以把每个单词看成是一条边，单词的首尾字符看做是两个相连的点。我们可以把它看成有向图的欧拉路径问题（欧拉路径，欧拉回路不太明白的自己百度吧）。
一个有向图含有欧拉通路，首先图是连通的，并且当且仅当该图所有顶点的入度 =出度， 或者起始顶点入度 = 出度 - 1 ，结束点 出度＝入度－１， 其余点入度＝ 出度。明白了这些，我们的思路也就清晰啦！
重点来啦：首先判断图是否连通的，在判断图是否存在欧拉路径，如果都符合那就找路径。
#include<iostream> #include<cstdio> #include<string.h> #include<cstring> #include<algorithm> using namespace std; 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; }