HDOJ 1181 变形课 dfs bfs 并查集 floyd传递闭包 四种姿势

缘起

虽说是简单题, 但是是经典题. 说它经典是因为它可以练习各种姿势~ HDOJ 1181 变形课

分析

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
变形课

Time Limit: 2000/1000 MS (Java/Others)    
Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 19380    Accepted Submission(s): 6975


Problem Description
呃......变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球
变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好
是使A物体变成B物体. 
Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变
成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且被迫听一大堆好好学习的道理.
 

Input
测试数据有多组。每组有多行，每行一个单词,仅包括小写字母,是Harry所会的所有咒语.数字0表示一组输入结束.
 

Output
如果Harry可以完成他的作业,就输出"Yes.",否则就输出"No."(不要忽略了句号)
 

Sample Input
so
soon
river
goes
them
got
moon
begin
big
0

Sample Output
Yes.

Hint 
Harry 可以念这个咒语:"big-got-them".
 

Source
Gardon-DYGG Contest 1
 
Recommend
JGShining

本题的输入很恶心, 一开始没读懂, 以为本题只需要处理一组数据. 其实是每组数据都以0结束.

姿势1 dfs

没什么好说的, 一个有向图, 图上26个顶点（a~z）, 每个单词就是一条弧————从首字母对应的顶点到尾字母的顶点. 然后问从b这个顶点出发能够到达m这个顶点吗? 其实就是从’b’这个顶点出发dfs搜索（注意，不是遍历而是搜索. 而且本题属于找到就不玩了的那种, 但其实视作遍历也行, 就是从’b’出发能不能遍历到’m’就行了嘛~, 但显然找到了就不玩了更加高效）

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
//#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
//#define LOCAL

vector<int> g[30];
bool v[30];
typedef vector<int>::iterator vit;

bool dfs(int i) // 当前处于i
{
	v[i] = true;
	if (i=='m'-'a')
	{
		return true; // 找到就不玩了
	}
	for (vit x = g[i].begin(); x!=g[i].end(); x++) // 拓展点
	{
		if (!v[*x])
		{
			if (dfs(*x))
			{
				return true;
			}
		}
	}
	return false;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	string a;
	while(cin>>a)
	{
		g[a[0]-'a'].push_back(a[a.length()-1]-'a');
		while(cin>>a)
		{
			if (a[0]=='0') // 读完一组数据了
			{
				dfs(1)?puts("Yes."):puts("No."); // 得出本组数据
				for (int i = 0;i<30; i++)
				{
					g[i].clear();
				}
				memset(v,0,sizeof(v)); // 清空之后准备下一组数据
				break;
			}
			g[a[0]-'a'].push_back(a[a.length()-1]-'a');  // 建图
		}
	}
	
	return 0;
}

ac情况

Status Accepted
Memory 1388kB
Length 935
Lang G++
Submitted 2019-10-07 22:17:16
Shared
RemoteRunId 30795150

姿势2 bfs

bfs也不用多说, 就是bfs遍历咯~ 从b出发能bfs到m就true, 否则就是false

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
//#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL

vector<int> g[30];
bool v[30];
typedef vector<int>::iterator vit;

bool bfs()
{
	queue<int> q;
	q.push(1);
	v[1] = true;
	while(!q.empty())
	{
		int front = q.front();
		q.pop();
		if (front=='m'-'a')
		{
			return true;
		}
		for (vit x = g[front].begin(); x!=g[front].end(); x++)
		{
			if (!v[*x])
			{
				v[*x] = true;
				q.push(*x);
			}
		}
	}
	return false;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	string a;
	while(cin>>a)
	{
		g[a[0]-'a'].push_back(a[a.length()-1]-'a');
		while(cin>>a)
		{
			if (a[0]=='0')
			{
				bfs()?puts("Yes."):puts("No.");
				for (int i = 0;i<30; i++)
				{
					g[i].clear();
				}
				memset(v,0,sizeof(v));
				break;
			}
			g[a[0]-'a'].push_back(a[a.length()-1]-'a');
		}
	}
	return 0;
}

ac情况

Status Accepted
Memory 1400kB
Length 976
Lang G++
Submitted 2019-10-07 22:20:26
Shared
RemoteRunId 30795231

姿势3 并查集

并查集的姿势也不消多说. 一个单词比如以x开头, 以y结尾, 则就表示y的老大是x. 所以只需读入所有的单词， 遇到b结尾的, 就不要维护了（因为最后是看b能不能变到m, b是要做老大的）. 其余的正常维护即可.

本题的并查集没有使用树上节点的个数进行维护（数据规模不大）

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
//#include "stdafx.h"
#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
//#define LOCAL

int f[30]; // 并查集

int getf(int i)
{
	return i==f[i]?i:f[i]=getf(f[i]);
}

void merge(int i,int j) // j认i做老大
{
	f[getf(j)] = getf(i);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	string a;
	while(cin>>a)
	{
		for (int i = 1;i<=26; i++)
		{
			f[i] = i;
		}
		int x = getf(a[0]-'a'+1), y =  getf(a[a.length()-1]-'a'+1); // x是首字母, y是尾字母, 如果y不是b的话, y认x做老大, 这里都要加1, 因为并查集是从1开始的,注意,这里要getf
		if (y!=2)
		{
			merge(x,y);
		}
		while(cin>>a)
		{
			if (a[0]=='0')
			{
				getf('m'-'a'+1)==2?puts("Yes."):puts("No.");
				break;
			}
			int x = getf(a[0]-'a'+1), y =  getf(a[a.length()-1]-'a'+1); // x是首字母, y是尾字母, 如果y不是b的话, y认x做老大, 这里都要加1, 因为并查集是从1开始的,注意,这里要getf
			if (y!=2)
			{
				merge(x,y);
			}
		}
	}
	return 0;
}

ac情况

Status Accepted
Memory 1380kB
Length 901
Lang G++
Submitted 2019-10-07 22:25:51
Shared
RemoteRunId 30795366

姿势4 floyd传递闭包

floyd求解有向图传递闭包
传递闭包—–所谓传递性，可以这样理解：对于一个节点i，如果j能到i，i能到k，那么j就能到k。求传递闭包，就是把图中所有满足这样传递性的节点都弄出来，计算完成后，我们也就知道任意两个节点之间是否有路径相通。

于是, 只需要读入所有单词, 然后初始化邻接矩阵（矩阵每个元素不是true就是false）. 然后跑floyd即可

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
//#include "stdafx.h"
#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
using namespace std;
//#define LOCAL

bool g[30][30];

void floyd()
{
	for (int k = 1; k<=26; k++)
	{
		for (int i = 1; i<=26; i++)
		{
			for (int j = 1; j<=26; j++)
			{
				g[i][j] = g[i][j] || g[i][k] && g[k][j]; // i本身就能到达j或者借助中间点k
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	string a;
	while(cin>>a)
	{
		memset(g,0,sizeof(g));
		int x = a[0]-'a'+1, y = a[a.length()-1]-'a'+1;
		g[x][y] = true;
		while(cin>>a)
		{
			if (a[0]=='0')
			{
				floyd(); // 跑floyd
				g['b'-'a'+1]['m'-'a'+1]?puts("Yes."):puts("No.");
				break;
			}
			int x = a[0]-'a'+1, y = a[a.length()-1]-'a'+1;
			g[x][y] = true;
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 15ms
Memory 1380kB
Length 806
Lang G++
Submitted 2019-10-07 22:38:35
Shared
RemoteRunId 30795746

恶搞姿势 （or2!）

1
2
3
4
5
6
#include<stdio.h>
int main()
{
	puts("Yes.\nNo.\nNo.");
	return 0;
}

ac情况

Status Accepted
Memory 1188kB
Length 68
Lang G++
Submitted 2019-10-08 06:29:27
RemoteRunId 30797655