本文主要是介绍10129 - Play on Words(欧拉道路有向图)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：10129 - Play on Words
题目大意：词语接龙。
解题思路：刚开始没想到欧拉道路，直接找，结果超时了。
这题满足要求的话就是把每个单词看做一条路，每条路连在一起走一遍就符合要求， 欧拉回路也是符合要求的。
满足欧拉道路：1，至多只有两个点的出度入度相差1。
2， 这个有向图的无向图连通。（刚开始一直在想，如果有两条一样的路，这样怎么处理，后面发现只要每个点都可以访问到就说明连通了）
#include<stdio.h>
#include<string.h>const int N = 26;
const int M = 1005;
int t, n;
int map[N][N], in[N], out[N], visit[N];
char word[M];void dfs(int x, int &m) {m++;visit[x] = 1;for(int i = 0; i < N; i++)if(map[x][i] && !visit[i]) {dfs(i, m);}
}int num_vertic() {int num = 0;for(int i = 0; i < N; i++)if(in[i] || out[i])num++;return num;
}int get_first() {for(int i = 0; i < N; i++)if(in[i] == 0 && out[i]) {for(int j = 0; j < N; j++)if(map[i][j]) return j;}
}int main() {scanf("%d", &t);while(t--) {scanf("%d", &n);int i, e, f;memset(map, 0, sizeof(map));memset(in, 0, sizeof(in));memset(out, 0, sizeof(out));memset(visit, 0, sizeof(visit));for(i = 0; i < n; i++) {scanf("%s", word);f = word[0] - 'a';e = word[strlen(word) - 1] - 'a';in[e]++;out[f]++;map[f][e] = 1;map[e][f] = 1;}int ok = 0;for(i = 0; i < N; i++) {if(in[i] - out[i] == 1 || out[i] - in[i] == 1) ok++;else if(in[i] != out[i]) {ok = -1;break;}}if(ok != 0 && ok != 2) printf("The door cannot be opened.\n");else {if(ok == 2)e = get_first(); ok = 0;dfs(e, ok);if(ok == num_vertic())printf("Ordering is possible.\n");elseprintf("The door cannot be opened.\n"); }}return 0;
}这篇关于10129 - Play on Words(欧拉道路有向图)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
