By yusijia

Updated:

Contents
  1. 1. 题目大意：
  2. 2. 分析：

题目链接

参考

题目大意：

找欧拉通路，还有个要求是要输出字典序最小的方案

分析：

  • 把每个单词的首字母和尾字母抽出来将单词作为一条边，

  • 要输出字典序最小的方案，其实对所有边从小到大排序就ok了，可以参考kruskal是怎样解决最小生成树的问题的

  • 然后用并查集 + set判单连通，再判断是欧拉回路还是不回到起点的欧拉通路

  • 接着dfs，回溯的时候把所有边压入栈中（注意是从终点往前起点方向，所以每次push的时候是push的最大的那条边，小的边留到靠近起点那，来产生最小字典序）

  • 最后输出路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

const int MAXN = 30;
int father[MAXN], inDegree[MAXN], outDegree[MAXN];
int n;
char word[1010][MAXN];
bool vis[1010];		//访问边
stack<char *> sta;	//存逆序路径
set<int> s;		//用来判连通性
vector<int > v[MAXN];	//存有向图

int cmp(const void *a, const void *b)
{
	return strcmp((char *)a, (char *)b);
}

void init()
{
	memset(inDegree, 0, sizeof(inDegree));
	memset(outDegree, 0, sizeof(outDegree));
	memset(word, 0, sizeof(word));
	memset(vis, false, sizeof(vis));
	for(int i = 0; i < MAXN; i++){
		father[i] = i;
		v[i].clear();//注意这里每次要初始化
	}
}

int finds(int x)
{
	return father[x] == x ? father[x]  : father[x] = finds(father[x]);
}

void unions(int x ,int y)
{
	int root_x = finds(x);
	int root_y = finds(y);
	father[root_y] = root_x;
}


//逆序push路径
void push(int x , int y){
    //push路径的时候是回溯时，所以是从终点往起点push，又因为要最小字典序，所以应该把大的边先push，
    for(int i = n - 1; i >= 0; i--){
       if(!vis[i] && word[i][0] - 'a' == x){
          if(y == word[i][strlen(word[i]) - 1] - 'a'){
             sta.push(word[i]);
             vis[i] = true;
             return;
          }
       }
    }
}

//计算欧道路
void dfs(int cur){
    while(!v[cur].empty()){
         int tmp = *(v[cur].begin());
         v[cur].erase(v[cur].begin());
         dfs(tmp);
         push(cur , tmp);
    }
}

//输出
void output(){
    while(!sta.empty()){
        printf("%s", sta.top());
        sta.pop();
        if(!sta.empty())
           printf(".");
    }
    printf("\n");
}


void solve()
{
	s.clear();
	for(int i = 0; i < MAXN; i++)if(vis[i]){
		s.insert(finds(i));
	}
	//printf("size: %d\n", s.size());
	if(s.size() > 1){
		printf("***\n")  ;
         		 return;
	}
	int sum = 0;
	for(int i = 0; i < MAXN; i++){
		if(abs(inDegree[i] - outDegree[i]) > 1){//出入度数差只能为1或0
			printf("***\n")  ;
         			 return;
		}
		if(abs(inDegree[i] - outDegree[i]) == 1)
			sum++;
	}
	if(!(sum == 0 || sum == 2)){//只有欧拉回路和不回到起点的欧拉通路
		printf("***\n");
		return ;
	}
	else{
		int start;
		for(int i = 0; i  < MAXN; i++){//找起点,如果是不回到起点的欧拉通路
			if(outDegree[i]-inDegree[i] == 1){//注意如果是这种欧拉通路，则起点的出度一定比入度大1，终点的入度一定比出度大1，而不是差的绝对值为1
				start = i;
				break;
			}
		}
		if(sum == 0){
			start = word[0][0] - 'a';//如果是欧拉回路的话从第一条边(最小)开始，来产生最小字典序
		}
		memset(vis , false , sizeof(vis));
		dfs(start);
		output();
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		init();
		for(int i = 0; i < n; i++)
			scanf("%s", word[i]);
		qsort(word, n, sizeof(word[0]), cmp);
		//for(int i = 0; i < n; i++)
                //printf("%s\n", word[i]);
		for(int i = 0; i < n; i++){
			int x = word[i][0] - 'a';
			int y = word[i][strlen(word[i]) - 1] - 'a';
			v[x].push_back(y);
			vis[x]  = vis [y] = true;
			inDegree[y]++;
			outDegree[x]++;
            		//printf("x, y : %d %d len = %d\n", x, y, strlen(word[i]));
			unions(x, y);
		}
		solve();
	}
	return 0;
}
Contents
  1. 1. 题目大意：
  2. 2. 分析：