LeetCode:547. Number of Provinces省份数量(C语言)

分手后的思念是犯贱 2023-01-03 04:19 52阅读 0赞

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

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

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

返回矩阵中 省份 的数量。

示例 1：  
![在这里插入图片描述][20210107111003663.jpg_pic_center]

输入：isConnected = \[\[1,1,0\],\[1,1,0\],\[0,0,1\]\]  
输出：2

示例 2：  
![在这里插入图片描述][20210107111010267.jpg_pic_center]

输入：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]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/number-of-provinces  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

void dfs(int** isConnected, int* visited, int provinces, int i) { 
        for (int j = 0; j < provinces; j++) { 
            if (isConnected[i][j] == 1 && !visited[j]) { 
                visited[j] = 1;
                dfs(isConnected, visited, provinces, j);
            }
        }
    }
    
    int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize) { 
        int provinces = isConnectedSize;
        int visited[provinces];
        memset(visited, 0, sizeof(visited));
        int circles = 0;
        for (int i = 0; i < provinces; i++) { 
            if (!visited[i]) { 
                dfs(isConnected, visited, provinces, i);
                circles++;
            }
        }
        return circles;
    }

**运行结果：**  
![在这里插入图片描述][20210107111029887.png_pic_center]

**Notes：**  
完全参照官方解答[https://leetcode-cn.com/problems/number-of-provinces/solution/sheng-fen-shu-liang-by-leetcode-solution-eyk0/][https_leetcode-cn.com_problems_number-of-provinces_solution_sheng-fen-shu-liang-by-leetcode-solution-eyk0]

[20210107111003663.jpg_pic_center]: /images/20221119/8a8cb220b3e840e799b0c62824280d4f.png
[20210107111010267.jpg_pic_center]: /images/20221119/1c1f8abb7f0841fd99b85d4b0257f491.png
[20210107111029887.png_pic_center]: /images/20221119/0449fa29d1e0474dab075234f7de4d0a.png
[https_leetcode-cn.com_problems_number-of-provinces_solution_sheng-fen-shu-liang-by-leetcode-solution-eyk0]: https://leetcode-cn.com/problems/number-of-provinces/solution/sheng-fen-shu-liang-by-leetcode-solution-eyk0/