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

HDUOJ 1181 变形课 这题方法很多:DFS、并查集都可!

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)]就可以啦!

今天拿了驾照,猴开森啦!

上一篇:Java 方法的重载(overload)


下一篇:Spring Security:用户服务UserDetailsService源码分析