猿辅导2021校招笔试真题

1、小猿的依赖循环

【题目描述】

小猿在加载一个网页，这个网页共需要N个相关资源，这些资源之间有一些依赖关系。如果这些资源中存在循环依赖，我们认为这个网页不能加载成功，否则可以加载成功。存在循环依赖是指，这些资源中存在资源X，X依赖的资源Y直接或间接依赖于X。

你能帮助小猿判断一下这个网页能否加载成功吗？

输入描述：

第一行输入T（T ≤ 10），表示输入T组数据。

每组数据第1行，输入一个数N（1 ≤ N ≤ 500）表示该组case有编号为1~N的N项资源。

每组数据第2到 N+1 行，输入一个 N*N 的零一矩阵。矩阵第 i 行第 j 列数字为 a[i][j] 表示编号为 i 的资源是否依赖于编号为 j 的资源，1表示依赖，0表示不依赖。数据保证a[i][i] = 0。

输出描述：

输出包含T行，每行输出对应每组case中是否存在循环依赖。存在输出1，不存在输出0。

输入样例：

2

3

0 1 0

0 0 1

1 0 0

3

0 1 0

0 0 0

0 0 0

输出样例：

1

0

说明：

第一组数据：1依赖于2，2依赖于3，3依赖于1，存在循环依赖。第二组数据：只有1依赖于2，不存在循环依赖。

【解题思路】
使用dfs优先遍历搜索来查看是否产生了循环。
注意事项：不能够直接dfs（0）,即所有的未走过的节点都要进行一次dfs，即图中的连通图的dfs遍历方式。即会有一种情况产生：a、b、c之间没有产生循环依赖，且a、b、c都没有依赖d和e，但是d和e却产生了依赖。但是如果只有一个dfs（0）就会产生错误，误以为这组数据没有产生循环依赖，事实却是产生了循环依赖，只是恰巧不在dfs（0）可以遍历到的范围之内罢了。

【参考代码】
#include<iostream>
using namespace std;
int n, t;
int p[505][505];
bool pd[505];
int ans = 0;
void init(int x) {
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < x; j++) {
			p[i][j] = 0;
		}
		pd[i] = false;
	}
	ans = 0;
}

void dfs(int x) {
	if (pd[x] == true) {
		ans = 1;
		return;
	}
	pd[x] = true;
	for (int i = 0; i < t; i++) {
		if (p[x][i] == 1) {
			dfs(i);
		}
	}
	pd[x] = false;
}
int main() {
	cin >> n;
	while (n != 0) {
		cin >> t;
		init(t);
		for (int i = 0; i < t; i++) {
			for (int j = 0; j < t; j++) {
				cin >> p[i][j];
			}
		}
		//dfs(0);
		//上面这行代码就是只从0这个点开始导致了错误。
		//下面这部分for循环代码就是为