ACM-ICPC寒假算法训练1：搜索：一道被输入方式卡住的一道简单题（方法多）

本文主要是介绍ACM-ICPC寒假算法训练1：搜索：一道被输入方式卡住的一道简单题（方法多），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目意思及算法分析：

这题吧，和咱们系oj的一道题很像，就是16级算法设计期末考试的时候，DU老师叫咱们去“虐”大三的那次考试，我们那道《简单图论题》没做出来，其实感觉和这个题没啥区别，那个题问能不能从一个点出发，跑出一个环（检查是否成环）。我们可以设一个DFS(i, j)代表从点 i 出发到达 j 的一条边，然后下一条边必然就是DFS(j, Next.i);这题感觉差不多嘞，主要分析的就是深度遍历的方式和条件，当我们下一个单词的头部能够和我们当前的单词尾部相连接的时候，就可以往后遍历，洛谷上有个差不多的题，叫单词接龙，挺好的一个题，可以去练习！

Solving code:

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

const int maxn = 10005;
struct TypeStruct {
	string contain;
	char First, Last;
}s[maxn];
int book, cnt, vis[maxn];
void dfs(int k) {
	if ('m' == s[k].Last) {
		book = 1;
		return;
	}
	if (cnt == k)
		return;
	for (int i = 0; i < cnt; i++) {
		if (s[i].First == s[k].Last && !vis[i]) {
			vis[i] = 1;
			dfs(i);
			vis[i] = 0;
		}
	}
}


int main() {
	string str;
	while (cin >> str) {
		if ("0" == str)
			continue;
		s[cnt].contain = str;
		int len = str.length();
		s[cnt].First = str[0], s[cnt].Last = str[len - 1];
		cnt++;
		while (cin >> str && "0" != str) {
			s[cnt].contain = str;
			len = str.length();
			s[cnt].First = str[0], s[cnt].Last = str[len - 1];
			cnt++;
		}
		for (int i = 0; i < cnt; i++) {
			if ('b' == s[i].First) {
				vis[i] = 1;
				dfs(i);
			}
		}
		if (book)
			cout << "Yes." << endl;
		else
			cout << "No." << endl;
		memset(vis, 0, sizeof(vis));
		cnt = book = 0;
	}
	return 0;
}

并查集思路：

其实也很简单，就是把26的单词，一开始p[0-25] = 0-25(p[i] = i).
然后，先让b开头的单词尾部的数字变成头部的，意味着能够实现b就能实现它，然后依次做合并，合并成最大联通图，然后查看p[1(b)] =? p[12(m)]就可以啦！

今天拿了驾照，猴开森啦！

这篇关于ACM-ICPC寒假算法训练1：搜索：一道被输入方式卡住的一道简单题（方法多）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！