题库>> 1021-图-找环
给定一个有向带权图A,找出图中的环,返回构成环的所有顶点,并按顶点从小到大排序。
约定:
(1)使用邻接矩阵表示图
(2)若两个顶点i,j相连则A[i][j]=1,否则A[i][j]=0
(3)顶点编号从0开始
(4)图是有向的,需要考虑方向性
(5)图中最多存在一个环

例如:
(1)
矩阵A的邻接矩阵表示为:
0,1,0
0,0,1
1,0,0

图中的环为:0,1,2
(2)
矩阵A的邻接矩阵表示为:
0,1,0
0,0,0
1,1,0

图中不存在环(方向问题):返回-1
输入、输出描述
输入:
A:有向图的邻接矩阵表示,若两个顶点i,j相连,则A[i][j]=1 否则A[i][j]=0
n:顶点的个数,顶点编号为:0,1,2...n-1
输出:
若存在环,则返回构成环的所有顶点,并按顶点从小到大排序。
若不存在环,则返回一个长度为1的数组,且元素值为-1
Example
输入:
A:
0,1,0
0,0,1
1,0,0
n:3
输出:
0,1,2
"Ctr-Q":自动补全
欢迎加算法刷题交流QQ群:474397739,每周刷题比赛,精美礼品等你拿!
评论专区
分享本文 微信公众号