AlgoPressAppearance
题目描述
https://leetcode.cn/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
提示：
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
思路
从第一个数字开始，找出所有和自己相关的城市，遍历完成后，省份加一。 然后从后面开始没有相连的城市再进行寻找 查找的方法可以使用 深度优先 和 广度优先
参考代码:深度优先
csharp
public class Solution {
private void dfs(int i, bool[] visited, int[][] isConnected){
for(int j=0; j<isConnected[i].Length; j++){
if(isConnected[i][j] == 1 && !visited[j]){
visited[j] = true;
dfs(j, visited, isConnected);
}
}
}
public int FindCircleNum(int[][] isConnected) {
int n = isConnected.Length;
bool[] visited = new bool[n];
int provinces = 0; //计算省份数量
for(int i=0; i<n; i++){
if(!visited[i]){
dfs(i,visited,isConnected);
provinces++;
}
}
return provinces;
}
}
参考代码：广度优先
需要使用队列
csharp
public class Solution{
public int FindCircleNum(int[][] isConnected){
int n = isConnected.Length;
bool[] visited = new bool[n];
int provinces = 0; //计算省份数量
Queue<int> queue = new Queue<int>();
//遍历节点，依次加入queue
for(int i=0; i<n; i++){
if(!visited[i]){
queue.Enqueue(i);
while(queue.Count > 0){
int k = queue.Dequeue();
visited[k] = true;
for(int j=0; j<n; j++){
if(isConnected[k][j] == 1 && !visited[j]){ //计算展开的第k行
queue.Enqueue(j);
}
}
}
provinces++;
}
}
return provinces;
}
}
参考题目：并查集
如果两个城市相连，就建立一个树的关系 将两棵树并在一起，查根节点
csharp
public class Solution{
public int FindCircleNum(int[][] isConnected){
int n = isConnected.Length;
int[] head = new int[n];
int[] level = new int[n];
for(int i=0; i<n; i++){
head[i] = i;
level[i] = 1;
}
//合并
for(int i=0; i<n; i++){
for(int j=+1; j<n;j++){
if(isConnected[i][j] == 1){
merge(i,j,head,level);
}
}
}
//查找
int provinces = 0;
for(int i=0; i<n; i++){
if(i == head[i]){
provinces++;
}
}
return provinces;
}
private void merge(int x, int y, int[] head, int[] level){
int i = find(x,head);
int j = find(y,head);
if(i == j){
return;
}
if(level[i] <= level[j]){
head[i] = j;
}
else{
head[j] = i;
}
if(level[i] == level[j]){
level[i]++;
level[j]++;
}
}
private int find(int x, int[] head){
if(head[x] == x)
{
return x;
}
head[x] = find(head[x],head);
return head[x];
}
}
复习：并查集 20220703
csharp
public class Solution {
public class UF{
private int[] parent;
private int[] size;
public UF(int n){
parent = new int[n];
size = new int[n];
for(int i=0;i<n; i++){
parent[i] = i;
size[i] = 1;
}
}
public void union(int p, int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP == rootQ){
return;
}
parent[rootP] = rootQ;
size[rootQ] = size[rootP] + size[rootQ];
}
public int find(int x){
//路径压缩
if(x != parent[x]){
parent[x] = find(parent[x]);
}
return parent[x];
}
}
public int FindCircleNum(int[][] isConnected) {
int n = isConnected.Length;
UF uf = new UF(n);
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(isConnected[i][j] == 1 && i!=j){
uf.union(i,j);
}
}
}
//遍历查找root节点
Dictionary<int,int> dict = new Dictionary<int,int>();
int count = 0;
for(int i=0; i<n; i++){
int key = uf.find(i);
if(!dict.ContainsKey(key)){
count++;
dict.Add(key,1);
}
}
return count;
}
}