作业二十八 单词拼接

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
 char s[31];
 int first, last;
};

node a[1001];
int degree_in[1001], degree_out[1001], m, order[1001];
bool used[1001];

int f()
{
 int x1, x2, ans = 0, i;
 x1 = x2 = 0;
 for (i = 0; i < 26; ++i)
 {
  if (abs(degree_in[i] - degree_out[i]) >= 2)
  return -1;
  else if (degree_in[i] - degree_out[i] == 1)
  x1++;
  else if (degree_in[i] - degree_out[i] == -1)
  {
   x2++;
   ans = i;
  }
 }
 if (x1>1 || x2 > 1) //当时三个度时，必定是 12 和21，相同的不能大于等于2，不然不能构成欧拉回路
 return -1;
 else if (x1 == 0)
 {
  for (i = 0; i < 26; ++i)
  if (degree_out[i])
  return i; //找到一个就行
 }
 else
 return ans;

}
bool cmp(node a, node b)
{
 return strcmp(a.s, b.s) < 0;
}

bool dfs(int st, int cnt)
{
 int i;
 if (cnt == m)
 return 1;
 for (i = 0; i < m; ++i)
 {
  if (a[i].first < st || used[i])
  continue;
  else if (a[i].first > st)
  return false;
  used[i] = true;
  order[cnt] = i;
  if (dfs(a[i].last, cnt + 1))
  return 1;
  used[i] = false;//回溯判断是否形成欧拉路径
 }
 return false;
}

int main()
{
 int N, len, i, start;
 scanf("%d", &N);
 while (N--)
 {
  memset(used, false, sizeof(used));
  memset(degree_out, 0, sizeof(degree_out));
  memset(degree_in, 0, sizeof(degree_in));
  scanf("%d", &m);
  for (i = 0; i < m; ++i)
  {
   scanf("%s", a[i].s);
   len = strlen(a[i].s);
   a[i].first = a[i].s[0] - 'a';
   a[i].last = a[i].s[len - 1] - 'a';
   degree_out[a[i].s[0] - 'a']++;
   degree_in[a[i].s[len - 1] - 'a']++;//注意这里的入肚出度
  }
  start = f();
  if (start == -1)
  {
   printf("***\n");
   continue;
  }
  sort(a, a + m, cmp);
  if (!dfs(start, 0))
  {
   printf("***\n");
   continue;
  }
  printf("%s", a[order[0]].s);
  for (i = 1; i < m; i++)
  printf(".%s", a[order[i]].s);
  printf("\n");
 }
return 0;
}