323. Number of Connected Components in an Undirected Graph

问题来自 323. Number of Connected Components in an Undirected Graph

---

初看之下，有两种方法可以解决该问题

1. 根据edges建图（adjacency list或者adjacency matrix），接着dfs或者bfs搜索
2. union-find（并查集）

leetcode运行结果显示union find最快，dfs邻接矩阵最慢

---

1, dfs或者bfs搜索图

下面的代码是dfs adjacency matrix：

class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        vector<vector<bool> > map(n, vector<bool>(n, false));
        int size = edges.size();
        for(int i = 0; i < size; ++i)
        {
            int u = edges[i].first;
            int v = edges[i].second;
            map[u][v] = map[v][u] = true;
        }
        
        vector<bool> visited(n, false);
        int count = 0;
        for(int u = 0; u < n; ++u)
            if(!visited[u])
            {
                visited[u] = true;
                dfs(n, u, map, visited);
                ++count;
            }
            
        return count;
    }
private:
    void dfs(int n, int u, vector<vector<bool> > &map, vector<bool> &visited)
    {
        for(int i = 0; i < n; ++i)
            if(map[u][i] && !visited[i])
            {
                visited[i] = true;
                dfs(n, i, map, visited);
            }
    }
};

下面的代码是adjacency list:

class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        vector<vector<int> > map(n, vector<int>());
        int size = edges.size();
        for(int i = 0; i < size; ++i)
        {
            int u = edges[i].first;
            int v = edges[i].second;
            map[u].push_back(v);
            map[v].push_back(u);
        }
        
        vector<bool> visited(n, false);
        int count = 0;
        for(int u = 0; u < n; ++u)
            if(!visited[u])
            {
                visited[u] = true;
                dfs(n, u, map, visited);
                ++count;
            }
            
        return count;
    }
private:
    void dfs(int n, int u, vector<vector<int> > &map, vector<bool> &visited)
    {
        int size = map[u].size();
        for(int i = 0; i < size; ++i)
        {
            int v = map[u][i];
            if(!visited[v])
            {
                visited[v] = true;
                dfs(n, v, map, visited);
            }
        }
    }
};

---

2, 并查集union-find

class Solution {
public:
    int countComponents(int n, vector<pair<int, int> >& edges) {
        root = vector<int>(n, -1);
        int size = edges.size();
        int count = n;
        for(int i = 0; i < size; ++i)
        {
            int u = edges[i].first;
            int v = edges[i].second;
            int uroot = findRoot(u);
            int vroot = findRoot(v);
            if(uroot != vroot)
            {
                --count;
                unionSet(uroot, u, vroot, v);
            }
        }
        
        return count;
    }
private:
    void unionSet(int uroot, int u, int vroot, int v)
    {
        root[uroot] = vroot;
    }
    int findRoot(int u)
    {
        if(root[u] == -1) return u;
        root[u] = findRoot(root[u]);
        return root[u];
    }
private:
    vector<int> root;
    
};

Java:

public class Solution {
    public int countComponents(int n, int[][] edges) {
        root = new int[n];
        for(int i = 0; i < n; ++i)
            root[i] = -1;
        int count = n;
        for(int i = 0; i < edges.length; ++i)
        {
            int u = edges[i][0];
            int v = edges[i][1];
            int uroot = findRoot(u);
            int vroot = findRoot(v);
            if(uroot != vroot)
            {
                --count;
                unionSet(uroot, u, vroot, v);
            }
        }
        return count;
    }
    private void unionSet(int uroot, int u, int vroot, int v)
    {
        root[uroot] = vroot;
    }
    private int findRoot(int u)
    {
        if(root[u] == -1) return u;
        root[u] = findRoot(root[u]);
        return root[u];
    }
    private int[] root;
}