Leetcode 323. Number of Connected Components in an Undirected Graph（python+cpp）

题目

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

解法1：DFS

• 每次DFS除去一条联通路，并且将DFS过程中已经访问过的节点放入set中
• 若当前访问的节点在之前的路径中已经被访问，证明当前节点属于已经产生的联通路中
• 否则从这个节点开始开辟一条新路径

class Solution:def countComponents(self, n: int, edges: List[List[int]]) -> int:helper(u):if u in pair:for v in pair[u]:if v not in visited:visited.add(v)helper(v)pair = collections.defaultdict(set)for u,v in edges:pair[u].add(v)pair[v].add(u)count = 0visited = set()for i in range(n):if i not in visited:helper(i)count+=1return count

时间复杂度：O(E), E为边的条数
空间复杂度：O(E+N),N为节点个数

解法2：unionfind

解析参见代码注释

class Solution:def countComponents(self, n: int, edges: List[List[int]]) -> int:def unionfind(p1,p2):nonlocal count# find root of p1while root[p1]!=p1:p1 = root[p1]# find root of p2while root[p2]!=p2:p2 = root[p2]#if roots of p1 and p2 are identicle, meaning they have already been mergedif root[p1]==root[p2]:return# merge them if not merged else:root[p1] = p2count -= 1# initially, we have n connected pathcount = n # store original rootsroot = [i for i in range(n)] # go through each node pairfor edge in edges:unionfind(edge[0],edge[1])return count

时间复杂度：有点想不清，欢迎留言
空间复杂度：O(N),N为节点个数

二刷c++版本

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;int countComponents(int n, vector<vector<int>>& edges){
    // use bfsvector<vector<int>> g(n);for(auto& edge : edges){
    g[edge[0]].push_back(edge[1]);g[edge[1]].push_back(edge[0]);}vector<int> visited(n,0);int ans = 0;for(int i=0;i<n;i++){
    if(visited[i] == 1) continue;queue<int> q;q.push(i);visited[i] = 1;while(!q.empty()){
    int curr = q.front();q.pop();for(auto& neigh : g[curr]){
    if(visited[neigh] == 0){
    q.push(neigh);visited[neigh] = 1;}}}ans += 1;}return ans;}int find(int p,vector<int>& root){
    while(p != root[p]){
    p = root[p];}return p;
}
void union_(int p,int q,vector<int>& root){
    int r1 = find(p,root);int r2 = find(q,root);cout << r1 << " " << r2 << endl;root[r1] = r2;
}
int countComponents2(int n, vector<vector<int>>& edges){
    // use union findvector<int> root(n,0);for(int i=0;i<n;i++){
    root[i] = i;}for(auto& edge : edges){
    union_(edge[0],edge[1],root);}set<int> count;for(auto num : root){
    count.insert(find(num,root));// cout << num << endl;}return count.size();
}int main()
{
    vector<vector<int>> edges{
    {
    0,1},{
    1,2},{
    3,4}};int n = 5;// vector<vector<int>> edges{
    {0,1},{1,2},{2,3},{3,4}};// int n = 5;int ans = countComponents2(5,edges);cout << "number of connected components = " << ans << endl;
}