hdu 3342 Legal or Not 拓扑排序板题

缘起

【1】中讲解了DAG图的拓扑排序、【2】中讲解了如何打印拓扑排序. 这里有必要写个高效的板子 hdu 3342 Legal or Not

分析

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
给出n个人的师徒关系，如有 a是b的师傅，b是c的师傅，c是a的师傅，这样则不合法，输出NO，否则输出YES。

【输入】
多样例. 对每个样例，第一行包含N和M（N是人的个数，M是关系的数量），然后M行 (x,y) 表明x是y的师傅,
y是x的徒弟. 最后N=0不用处理。每个人编号为0~N-1
(2 <= N, M <= 100)

【输出】
YES或者NO

【样例输入】
3 2
0 1
1 2
2 2
0 1
1 0
0 0

【样例输出】
YES
NO

【限制】
1s

【来源】
hdu月赛

红果果的判断是否是DAG. 既可以使用拓扑排序也可以使用dfs（参见【3】）

这里就为一块板子而已.

拓扑排序

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

int n,m,indeg[105],g[105][105];

int topsort()
{
	int nn = n;
	stack<int> s;
	for (int i = 0; i<n; i++)
	{
		if (!indeg[i])
		{
			s.push(i);
		}
	} // 初始化栈
	while(!s.empty())
	{
		int top = s.top(); // 入度为0的点
		s.pop(); // 出栈顺序就是一种拓扑序
		nn--;
		for (int i = 0; i<n; i++)
		{
			if (g[top][i] && !--indeg[i])
			{
				s.push(i);
			}
		}
	}
	return nn;
}

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(scanf("%d", &n), n)
	{
		memset(indeg, 0, sizeof(indeg));
		memset(g, 0, sizeof(g));
		scanf("%d", &m);
		while(m--)
		{
			int a,b;
			scanf("%d%d", &a, &b);
			if (!g[a][b]) // 此题数据有重弧! wa到吐~
			{
				g[a][b] = 1;
				indeg[b]++;
			}
		}
		topsort()?puts("NO"):puts("YES"); // 如果减到0了, 则表明是DAG，否则不是
	}
	return 0;
}

ac情况

Status Accepted
Time 46ms
Memory 1308kB
Length 867
Lang G++
Submitted 2019-09-08 06:46:41
Shared
RemoteRunId 30529000

dfs

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
67
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

int n,m,g[105][105];
bool v[105],mark[105]; // dfs判断DAG需要两个bool数组, v用于哈希搜索路径上的点,mark用于防止搜索到别的深搜树上去,v是要改回来的, mark是不需要改回来的

bool dfs(int i) // 返回true表示有环,false表示无环
{
	if (v[i]) // 如果搜到了该搜索路径上之前就搜到过的点了,则一定存在环, 不是DAG,
	{
		return true;
	}
	if (mark[i]) // 如果搜到的不是一路来的搜索路径上的点而是别的已经搜过的深搜树上的点,则此搜索路径一定不存在环,要是能存在环的话, 则就不会在不同的深搜树上了,
	{
		return false;
	} // 上面这两行判断显然是不能反过来的,这在【3】中也说过了, 因为已经搜过的顶点的mark一定是true啊(看下面一行代码)
	v[i] = mark[i] = true;
	for (int j = 0; j<n; j++)
	{
		if (g[i][j])
		{
			if (dfs(j))
			{
				return true;
			}
		}
	}
	v[i] = false; // 搜索的话要记得改回来
	return false;
}

bool xxx()  // 返回true表示有环,否则无环
{
	for (int i = 0; i<n;i++)
	{
		if (dfs(i))
		{
			return true;
		}
	}
	return false;
}

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(scanf("%d", &n), n)
	{
		memset(g, 0, sizeof(g));
		memset(v, 0, sizeof(v));
		memset(mark, 0, sizeof(mark));
		scanf("%d", &m);
		while(m--)
		{
			int a,b;
			scanf("%d%d", &a, &b);
			g[a][b] = 1;
		}
		xxx()?puts("NO"):puts("YES");
	}
	return 0;
}

ac情况（果然dfs比拓扑排序更快!）

Status Accepted
Time 15ms
Memory 1264kB
Length 1108
Lang G++
Submitted 2019-09-08 07:05:56
Shared
RemoteRunId 30529008

参考

【1】https://yfsyfs.github.io/2019/05/21/%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F/

【2】https://yfsyfs.github.io/2019/05/21/%E5%85%B3%E9%94%AE%E8%B7%AF%E5%BE%84/

【3】https://yfsyfs.github.io/2019/05/21/DAG%E5%88%A4%E5%AE%9A%E7%9A%84%E9%99%A4%E6%8B%93%E6%89%91%E5%BA%8F%E4%B9%8B%E5%A4%96%E7%9A%84%E5%8F%A6%E4%B8%80%E7%A7%8D%E6%96%B9%E6%B3%95/