成都建站网站,网站名字做版权需要源代码吗,2013网站建设方案,免费的韩国网站服务器活动 - AcWing
有 N 个盘子#xff0c;每个盘子上写着一个仅由小写字母组成的英文单词。
你需要给这些盘子安排一个合适的顺序#xff0c;使得相邻两个盘子中#xff0c;前一个盘子上单词的末字母等于后一个盘子上单词的首字母。
请你编写一个程序#xff0c;判断是否能…活动 - AcWing
有 N 个盘子每个盘子上写着一个仅由小写字母组成的英文单词。
你需要给这些盘子安排一个合适的顺序使得相邻两个盘子中前一个盘子上单词的末字母等于后一个盘子上单词的首字母。
请你编写一个程序判断是否能达到这一要求。
输入格式
第一行包含整数 T表示共有 T 组测试数据。
每组数据第一行包含整数 N表示盘子数量。
接下来 N 行每行包含一个小写字母字符串表示一个盘子上的单词。
一个单词可能出现多次。
输出格式
如果存在合法解则输出”Ordering is possible.”否则输出”The door cannot be opened.”。
数据范围
1≤N≤105 单词长度均不超过1000
输入样例
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok输出样例
The door cannot be opened.
Ordering is possible.
The door cannot be opened.
解析
一、在无向图中所有边都是连通的
1存在欧拉路径的充分必要条件度数为奇数的点只能有0或2。
2存在欧拉回路起点和终点相同的充分必要条件度数为奇数的点只能有0个。
二、在有向图中所有边都是连通的
1存在欧拉路径的充分必要条件要么所有点的入度均等于入度要么除了两个点之外其余所有的点的出度等于入度剩余的两个点一个满足出度比入度多1起点另一个满足入度比出度多1终点。
2存在欧拉回路起点和终点相同的充分必要条件所有点的入度均等于出度。
欧拉回路的dfs用边来判重不能用点。
本题的建图方式与《单词环》很像1165. 单词环 (01分数规划建图经验值优化正环)-CSDN博客
1.建图将每个字符串看成一条边边的两个端点为字符串首尾的两个字符
然后再根据上述概念判断是否存在欧拉路径即可。
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pairint, int PII;
const int N 30, M 2e3, INF 0x3f3f3f3f;
int n, m;
int din[N], dout[N], st[N];
int p[N];int find(int u) {if (p[u] u)return u;return p[u] find(p[u]);
}int main() {int T;cin T;while (T--) {cin n;memset(st, 0, sizeof st);memset(din, 0, sizeof din);memset(dout, 0, sizeof dout);for (int i 0; i 26; i)p[i] i;char s[M];for (int i 1; i n; i) {scanf(%s, s);int len strlen(s);int a s[0] - a, b s[len - 1] - a;din[a], dout[b];p[find(a)] find(b);st[a] st[b] 1;}int start 0, end 0;int success 1;for (int i 0; i 26; i) {if (din[i] ! dout[i]) {if (din[i] dout[i] 1)end;else if (din[i] 1 dout[i])start;else {success 0;break;}}}if (success !(!start !end || start 1 end 1))success 0;int rep -1;for (int i 0; i 26; i) {if (st[i]) {if (rep -1)rep find(i);else if (rep ! find(i)) {success 0;break;}}}if (success)cout Ordering is possible. endl;else cout The door cannot be opened. endl;}return 0;
}
