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练习
投递字节跳动等公司7个岗位 >
游卡公司福利 173人发布
查看19道真题和解析