此博客链接：https://www.cnblogs.com/ping2yingshi/p/14249611.html
题目链接：https://leetcode-cn.com/problems/number-of-provinces/
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例 2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
此题的意思是相连的城市会组成一个省份，最后问你有几个省份，给的n表示城市，连着的城市组成一个省份，像数据结构中图的连通分量。
思路：采用深度优先搜索遍历，从一个城市开始遍历，把遍历过的城市标记为1，直到从当前城市一直遍历到不能在遍历为止，标记为1的城市组成一个省份。
class Solution { public int findCircleNum(int[][] isConnected) { int count=0; boolean viseted[]=new boolean[isConnected.length]; for(int i=0;i<isConnected.length;i++) { if(!viseted[i]) { dfs(isConnected,viseted,isConnected.length,i); count++; } } return count; } public void dfs(int[][] isConnected,boolean viseted[],int length,int i) { for(int j=0;j<length;j++) { if(isConnected[i][j]==1&&!viseted[j])//true表示没有遍历 { viseted[j]=true; dfs(isConnected,viseted,isConnected.length,j); } } } }
原文：https://www.cnblogs.com/ping2yingshi/p/14249611.html