547. 省份数量

问题547 省份数量 ★★☆☆☆

https://leetcode-cn.com/problems/number-of-provinces/

这个题目和问题130-被围绕的区域、问题200-岛屿数量有一些相似之处，问题130和问题200这些题目里，每个元素是独立的个体，以自身的值为依据做连通。而这个题目里元素值表示的是这些个体之间是否连通，等于是给了一个图，要计算的是有多少连通的子图。对图算法敏感的话，应该第一时间就明白这是计算图的连通分量数目。从代码的角度看，Problem130、Problem200是以二维数组的每个元素为粒度做DFS，这个题目是以图的节点为粒度做DFS。

	public int findCircleNum(int[][] isConnected) {
		int len = isConnected.length;

		boolean[] visited = new boolean[len];

		int num = 0;
		for (int i = 0; i < len; i++) {
			if (!visited[i]) {
				num++;
				dfs(isConnected, visited, i);
			}
		}

		return num;
	}

	private void dfs(int[][] isConnected, boolean[] visited, int i) {
		visited[i] = true;
		for (int j = 0; j < isConnected.length; j++) {
			if (isConnected[i][j] == 1
				&& !visited[j]) {
				dfs(isConnected, visited, j);
			}
		}
	}

在 LeetCode 查看