题目
有 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
解题
方法一：并查集
class UnionFind{ private: vector<int> parent; int setNum; public: UnionFind(int n){ parent.resize(n); iota(parent.begin(),parent.end(),0); setNum=n;//初始集合数量为n } int find(int index){ if(parent[index]==index) return index; parent[index]=find(parent[index]); return parent[index]; } void unite(int index1,int index2){ int p1=find(index1); int p2=find(index2); if(p1!=p2){//如果两个集合不是同一个，那么合并集合，集合数量减一 parent[p1]=p2; setNum--; } } int getSetNum(){ return setNum; } }; class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { int n=isConnected.size(); UnionFind uf(n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(isConnected[i][j]==1){ uf.unite(i,j); } } } return uf.getSetNum(); } };
方法二：dfs
class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { int n=isConnected.size(); int res=0; vector<bool> visit(n); for(int i=0;i<n;i++){ if(!visit[i]){ dfs(isConnected,visit,i); res++; } } return res; } void dfs(vector<vector<int>>& isConnected,vector<bool>& visit,int i){ visit[i]=true; for(int j=0;j<visit.size();j++){ if(!visit[j]&&isConnected[i][j]){ dfs(isConnected,visit,j); } } } };
