讨论/《深度优先搜索》 - 例题:无向图中连通分量的数目/
《深度优先搜索》 - 例题:无向图中连通分量的数目
共 10 个回复

输入4,一共有四个点:0,1,2,3
根据2维数组1,2,3是互通的一个环,0是单独一个点,所以结果是2

1
class Solution {
public:
    void dfs(int node, vector<bool>& visited,  map<int, set<int>>& graph){
        visited[node]=true;
        for(auto neighbor: graph[node]){
            if(!visited[neighbor])
                dfs(neighbor,visited, graph);
        }
    }
    int countComponents(int n, vector<vector<int>>& edges) {
        map<int, set<int>> graph;
        vector<bool> visited(n);
        for(const auto& edge: edges){
            graph[edge[0]].insert(edge[1]);
            graph[edge[1]].insert(edge[0]);
        }
        int count=0;
        for(int i=0; i<n; i++){
            if(!visited[i]){
                dfs(i,visited, graph);
                count++;
            }
        }
        return count;
    }
};
1

?? 啥意思 0?

0没有被连上呀

20210408100452.jpg

这个用例是个环结果不应该是1么 怎么是2呢?

并查集
class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] root = new int[n];
        for (int i = 0; i < n; i++) {
            root[i] = i;
        }
        for (int[] edge : edges) {
            int findx = find(root, edge[0]);
            int findy = find(root, edge[1]);
            if (findx != findy) {
                union(root, findx, findy);
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (root[i] == i) {
                System.out.println(root[i]);
                res++;
            }
        }
        return res;
    }

    private int find(int[] root, int x) {
        while (root[x] != x) {
            x = root[x];
        }
        return x;
    }

    private void union(int[] root, int x, int y) {
        int findx = find(root, x);
        int findy = find(root, y);
        if (findx != findy) {
            root[findx] = findy;
        }
    }
}
var countComponents = function(n, edges) {
    const uf = new UnionFind(n);
    edges.forEach(e=>{
        uf.union(...e)
    })
    return uf.count;
};
class UnionFind{
    constructor(n){
        this.fa = new Array(n).fill(0).map((e,i)=>i);
        this.count = n;
        this.size = new Array(n).fill(1);
    }
    find(x){
        return this.fa[x] === x ? x : (this.fa[x] = this.find(this.fa[x]))
    }
    union(x,y){
        let rootX = this.find(x), rootY = this.find(y);
        if(rootX === rootY) return;
        if(this.size[rootX] < this.size[rootY]){
            [rootX, rootY] = [rootY, rootX]
        }
        this.fa[rootY] = rootX;
        this.size[rootX] += this.size[rootY];
        this.count--;
    }
}
class Solution(object):
    def countComponents(self, n, edges):
        dt = defaultdict(list)
        for e in edges:
            dt[e[0]].append(e[1])
            dt[e[1]].append(e[0])
        vstd = res = 0
        for i in range(n):
            if not vstd & (1 << i):
                vstd |= (1 << i)
                res += 1
                q = [i]
                while q:  
                    cur = q.pop(0)
                    for nxt in dt[cur]:
                        if not vstd & (1 << nxt):
                            vstd |= (1 << nxt)
                            q.append(nxt)
        return res
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        p = {}
        cnt = n
        def find(x):
            p.setdefault(x,x)
            while x != p[x]:
                x = p[x]
            return x
        def union(x,y):
            nonlocal cnt
            if connected(x,y): return
            p[find(x)] = find(y)
            cnt -= 1
        def connected(x,y):
            return find(x) == find(y)
        def add(x):
            if x not in p:
                p[x] = None
                # cnt += 1
        for edge in edges:
            union(edge[0],edge[1])
        return cnt
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        dt = defaultdict(list)
        for edge in edges:
            dt[edge[0]].append(edge[1])
            dt[edge[1]].append(edge[0])
        res = vstd = 0
        def dfs(i):
            nonlocal vstd
            for j in dt[i]:
                if not vstd & (1 << j):
                    vstd |= (1 << j)
                    dfs(j)
        for i in range(n):
            if not vstd & (1 << i):
                res += 1
                vstd |= (1 << i)
                dfs(i)
        return res