题库>> 1023-图-最大强连通子图
在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量。给定有向图A的邻接矩阵表示,若顶点i,j之间有边则A[i][j]=1 , 否则A[i][j]=0,求最大强连通子图,返回该最大强连通子图的顶点,按顶点值由小到大排列。
约定:
(1)最大连通子图唯一
输入、输出描述
输入:
A:有向图的邻接矩阵表示,若顶点i,j之间有边则A[i][j]=1, 否则A[i][j]=0
n:顶点的个数,顶点编号为:0,1,2...n-1
输出:
最大强连通子图中的顶点构成的数组,按顶点值由小到大排列。
Example
输入:
A:
0,0,1,0,0
0,0,0,0,0
0,0,0,1,1
0,0,0,0,1
1,0,1,0,0

n:5
输出:
0,2,3,4
"Ctr-Q":自动补全
欢迎加算法刷题交流QQ群:474397739,每周刷题比赛,精美礼品等你拿!
评论专区
分享本文 微信公众号