省份数量

题目

思路

• 并查集：通过并查集这种数据结构，得到若干个子集，子集的个数就是对应城市的个数

• 深度优先：递归搜索出直接或间接相连的节点直到再也没有节点与这条关系链上的节点有关联为止，这就得出了一个城市，标记这些已被访问点，重复刚才的操作直到所有节点都被标记位置。

  代码

  ```java //1.并查集做法 int res = 0; public int findCircleNum(int[][] isConnected) {

    int[] s = new int[isConnected.length];
    res = isConnected.length;
    //初始化
    Arrays.fill(s, -1);
    //构建并查集
    for (int i = 0; i < s.length; i++) {
        for (int j = 0; j < s.length; j++) {
            if (isConnected[i][j] > 0) union(s, i, j);
        }
    }
    return res;

  }

  //合并操作 public void union(int[] s, int i, int j) {

    if (i < 0 || j < 0 || i >= s.length || j >= s.length) return;
    int ri = findFC(s, i), rj = findFC(s, j);
    if (ri != rj) {
        s[ri] = rj;
        res--;
    }
  

  }

  //采用路径压缩查找 public int findFC(int[] s, int i) {

    if (i < 0 || i >= s.length) return -1;
    if (s[i] < 0) return i;
    s[i] = findFC(s, s[i]);
    return s[i];
  

  }

//2.dfs把直接间接连接在一起的都计算出来就得到一个城市，下一次这些就不能在访问了
public int findCircleNum(int[][] isConnected) {
    boolean[] visted = new boolean[isConnected.length];
    int res = 0;
    for (int i = 0; i < visted.length; i++) {
        if (!visted[i]) {
            dfs(isConnected, visted, i);
            res++;
        }
    }
    return res;
}

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

``` 省份数量