塔子哥最近扩展了快递服务,快递业务范围有 N 个站点,如果 A 站点与 B 站点可以中转快递,则认为 A−B 站可达,如果 A−B 可达, B−C 可达,则 A−C 可达。现在给 N 个站点编号 0、1、…n−1 ,用 s[i][j] 表示 i−j 是否可达, s[i][j]=1 表示 i−j 可达, s[i][j]=0 表示 i−j 不可达。
这道题就是求二维矩阵的连通块个数,或者是说大家比较熟悉的“岛屿问题”。我们只需遍历整个图,每次以一个未被遍历过的图为起点,用dfs或bfs
将与它相连通的点统计起来,我们可以用并查集判断两个点时候联通。但在这份题解中,我们直接将联通的点放入一个集合中,也能达到目的,不过相较于
并查集时间复杂度会稍高,同时采用dfs遍历。
本题属于以下题库,请选择所需题库进行购买