首页 > 2021绿皮书技术类公共题目-编程题讲解-并查集
头像
晗江雪
编辑于 2021-09-09 12:11
+ 关注

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,不存在循环依赖。


点击链接查看视频讲解与线上OJ练习



完整绿皮书纸质版免费领取:



全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

热门推荐