个人中心
gpt4 book ai didi

323. Number of Connected Components in an Undirected Graph 无向图中连通分量的数目

转载 作者：大佬之路 更新时间：2024-01-31 14:20:27 24 4
gpt4 key购买 nike

题目地址：https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph/

题目描述

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.

Example 1:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4 

Output: 2

Example 2:

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4
     |           |
     1 --- 2 --- 3

Output:  1

Note:

Youcan assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

题目大意

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。

解题方法

并查集

看到求联通分量的题，一般都可以用并查集。比如1101. The Earliest Moment When Everyone Become Friendsopen in new window。

只要把并查集背下来，这个题目基本直接写上去就好了。

C++代码如下：

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        map_ = vector<int>(n, 0);
        components = n;
        for (int i = 0; i < n; ++i) {
            map_[i] = i;
        }
        for (vector<int>& edge : edges) {
            uni(edge[0], edge[1]);
        }
        return components;
    }
    int find(int a) {
        if (a == map_[a])
            return a;
        return find(map_[a]);
    }
    void uni(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb)
            return;
        map_[pa] = pb;
        components --;
    }
private:
    vector<int> map_;
    int components;
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

2022

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发

24 4 0
文章推荐： 205. Isomorphic Strings 同构字符串
文章推荐： 320. Generalized Abbreviation 列举单词的全部缩写
文章推荐： 121. Best Time to Buy and Sell Stock 买卖股票的最佳时机
文章推荐： 244. Shortest Word Distance II 最短单词距离 II
大佬之路
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com