547.省份数量

题目

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

题解

方法一：使用DFS计算无向连通图的连通分量个数

DFS递归，思路简单，也没有太大的改变

include <iostream>
#include <vector>
using namespace std;
class Solution
{

public:
  void dfs(vector<vector<int>> &isConnected, int i,vector<int>& visited){
    visited[i]=1; // 标记当前节点为已访问
    for(int j=0;j<isConnected[i].size();j++){
      if(isConnected[i][j]==1&& visited[j]==0){ // 如果是连通的且未访问
        dfs(isConnected,j,visited); // 递归访问
      }
    }
  }

  int findCircleNum(vector<vector<int>> &isConnected)
  {
    // isConnected是无向连通图的邻接矩阵
    int n = isConnected.size();
    vector<int> visited(n, 0); // 访问标记
    int cnt = 0;               // 省份数

    for (int i = 0; i < n; i++)
    {
      if (!visited[i])
      {
        cnt++;                        // 发现一个新的省份
        dfs(isConnected, i, visited); // 深度优先搜索
      }
    }
    return cnt; // 返回省份数
  }
};

方法二：用并查集的方法

主要步骤

把每个城市都设为一个节点，初始化父节点都为自己
遍历邻接矩阵，当发现_isConnect [i][j ] == 1 时，说明这两个城市在一个省内
检查它们的根节点，如果根节点不同，用Union把它们合并，并把size–
最后size的值即为结果

class UnionFind
{
public:
  vector<int> parent;
  int size;

  UnionFind(int n)
  {
    parent.resize(n);
    for (int i = 0; i < n; i++)
    {
      parent[i] = i;
    }
    size = n;
  }

  int Find(int i)
  {
    if (parent[i] == i)
      return i;
    return parent[i] = Find(parent[i]); // 路径压缩
  }
  void Union(int p, int q)
  {
    int rootp = Find(p);
    int rootq = Find(q);
    if (rootp != rootq)
    {
      parent[rootp] = rootq; // 将p的根节点指向q的根节点
      size--;
    }
  }
};

class Solution
{
public:
  int findCircleNum(vector<vector<int>> &isConnected)
  {
    int n = isConnected.size();
    UnionFind *uf = new UnionFind(n); // 初始化并查集
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
      {
        if (isConnected[i][j] == 1)
        {
          uf->Union(i, j); // 如果i和j是连通的，合并它们
        }
      }
    }
    return uf->size; // 返回连通分量的数量
  }
};

优化版的题解

本来写写基本方法就觉得已经够了，但我寻思当时我也浅研究了一下并查集的优化，于是决定补充完整。

1. 按秩合并 + 路径压缩

class UnionFind {
public:
    vector<int> parent, rank;
    int size;
    UnionFind(int n) : parent(n), rank(n, 0), size(n) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int Find(int i) {
        if (parent[i] != i) parent[i] = Find(parent[i]);
        return parent[i];
    }
    void Union(int p, int q) {
        int rootp = Find(p), rootq = Find(q);
        if (rootp == rootq) return;
        if (rank[rootp] < rank[rootq]) parent[rootp] = rootq;
        else if (rank[rootp] > rank[rootq]) parent[rootq] = rootp;
        else { parent[rootq] = rootp; rank[rootp]++; }
        size--;
    }
};

2. 遍历邻接矩阵时只遍历上三角

由于 isConnected (是对称矩阵（无向图），可以只遍历j > i的部分，避免重复合并，减少一半的遍历次数。

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (isConnected[i][j] == 1) {
            uf->Union(i, j);
        }
    }
}

3.其它

有一种优化的方法是让根节点的parent数组的值为负数，负数的绝对值即为秩的大小（树高或总节点数）。
这样一个parent数组就可以搞定一切。

class UnionFind
{
public:
    vector<int> parent;
    int size;

    UnionFind(int n)
    {
        parent.resize(n);
        for (int i = 0; i < n; i++)
        {
            parent[i] = -1; // 每个集合初始大小为1
        }
        size = n;
    }

    int Find(int i)
    {
        if (parent[i] < 0)
            return i;
        return parent[i] = Find(parent[i]); // 路径压缩
    }

    void Union(int p, int q)
    {
        int rootp = Find(p);
        int rootq = Find(q);
        if (rootp == rootq) return;
        // 小树合并到大树
        if (parent[rootp] < parent[rootq]) {
            parent[rootp] += parent[rootq]; // 更新根节点的秩（负数，节点数相加）
            parent[rootq] = rootp;          // rootq指向rootp
        } else {
            parent[rootq] += parent[rootp];
            parent[rootp] = rootq;
        }
        size--;
    }
};