jjzjj

leetcode 547. Number of Provinces 省份数量(中等)

okokabcd 2023-03-28 原文

一、题目大意

标签:搜索

https://leetcode.cn/problems/number-of-provinces

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

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

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

返回矩阵中 省份 的数量。

示例 1：

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

示例 2：

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

二、解题思路

每个人看作是一个点，每个人与他人的联系看作是一条线，即n条线，包括自己与自己的关系。这样每个节点最多n条边最少1条边。

三、解题方法

3.1 Java实现

public class Solution {
    public int findCircleNum(int[][] isConnected) {
        int M = isConnected.length;
        int num = 0;
        boolean[] visited = new boolean[M];
        for (int i = 0; i < M; i++) {
            if (!visited[i]) {
                dfs(isConnected, i, visited);
                num++;
            }
        }

        return num;
    }

    private void dfs(int[][] isConnected, int i, boolean[] visited) {
        visited[i] = true;
        for (int j = 0; j < isConnected[0].length; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                dfs(isConnected, j, visited);
            }
        }
    }
}

四、总结小记

  • 2022/6/1 白天越来越长，四川雅安连发地震 最大6.1级。。。
ProvincesleetcodeisConnected相连visited算法与数据结构

有关leetcode 547. Number of Provinces 省份数量(中等)的更多相关文章

  1. HBase Region 简介和建议数量&大小 - 2

    Region是HBase数据管理的基本单位,region有一点像关系型数据的分区。region中存储这用户的真实数据，而为了管理这些数据，HBase使用了RegionSever来管理region。Region的结构hbaseregion的大小设置默认情况下，每个Table起初只有一个Region，随着数据的不断写入，Region会自动进行拆分。刚拆分时，两个子Region都位于当前的RegionServer，但处于负载均衡的考虑，HMaster有可能会将某个Region转移给其他的RegionServer。RegionSplit时机：当1个region中的某个Store下所有StoreFile

  2. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  3. ruby-on-rails - 设计中的 ArgumentError::RegistrationsController#new 错误的参数数量(2 代表 0..1) - 2

    我在关注RyanbatesRailsCast的devise和omniauth(第235集-devise-and-omniauth-revised)。当我尝试使用Twitter登录时，标题中不断出现错误。defself.new_with_session(params,session)ifsession["devise.user_attributes"]new(session["devise.user_attributes"],without_protection:true)do|user|user.attributes=paramsuser.valid?end完整跟踪:C:/Ruby20

  4. ruby-on-rails - 在 osx 10.9.3 上使用 RVM 安装 ruby​​-1.9.3-p547 时出错 - 2

    如何解决这个错误:$rvminstall1.9.3Searchingforbinaryrubies,thismighttakesometime.Nobinaryrubiesavailablefor:osx/10.9/x86_64/ruby-1.9.3-p547.Continuingwithcompilation.Pleaseread'rvmhelpmount'togetmoreinformationonbinaryrubies.Checkingrequirementsforosx.Certificatesin'/usr/local/etc/openssl/cert.pem'arealr

  5. ruby-on-rails - 如何计算 Ruby/Rails 中 JSON 对象的数量 - 2

    Ruby中如何“一般地”计算以下格式(有根、无根)的JSON对象的数量？一般来说，我的意思是元素可能不同(例如“标题”被称为其他东西)。没有根:{[{"title":"Post1","body":"Hello!"},{"title":"Post2","body":"Goodbye!"}]}根包裹:{"posts":[{"title":"Post1","body":"Hello!"},{"title":"Post2","body":"Goodbye!"}]} 最佳答案 首先，withoutroot代码不是有效的json格式。它将没有包

  6. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  7. ruby - 如何正确解析不同数量的命令行参数 - 2

    n00b问题警报!这是问题所在:我正在创建一个至少包含3个参数的shell脚本:一个字符串、一个行号和至少一个文件。我已经编写了一个脚本，可以接受EXACTLY3个参数，但我不知道如何处理多个文件名参数。这是我的代码的相关部分(跳过写回文件等):#!/usr/bin/envrubythe_string=ARGV[0]line_number=ARGV[1]the_file=ARGV[2]definsert_script(str,line_n,file)f=files=strln=line_n.to_iif(File.file?f)read_in(f,ln,s)elseputs"false

  8. python - 如何计算文件中唯一字符的数量？ - 2

    给定一个包含各种语言字符的UTF-8文件，我如何计算它包含的唯一字符的数量，同时排除选定数量的符号(例如:“!”、“@”、"#",".")从这个算起？ 最佳答案 这是一个bash解决方案。:)bash$perl-CSD-ne'BEGIN{$s{$_}++forsplit//,q(!@#.)}$s{$_}++||$c++forsplit//;END{print"$c\n"}'*.utf8 关于python-如何计算文件中唯一字符的数量？，我们在StackOverflow上找到一个类似的问题

  9. ruby - 查找字符串中唯一元素数量的最快方法 - 2

    如何以最佳方式在字符串中找到唯一元素？示例字符串格式为myString="34345667543"对/对['3','4','3','5'.....] 最佳答案 这是一个有趣的问题，因为它返回了很多几乎相似的结果，所以我做了一个简单的基准测试来决定哪个实际上是最好的解决方案:require'rubygems'require'benchmark'require'set'puts"Dothetest"Benchmark.bm(40)do|x|STRING_TEST="26263636362626218118181111232112233"

  10. ruby-on-rails - 在具有 enum_attr 的记录上调用 .all 时参数数量错误 - 2

    MODEL1有一个account_type，所以使用gem'enumerated_attributes'，我制作了这样的模型:classMODEL1我不明白的奇怪的事情是，当我像这样查询任意MODEL1的种子时(这是我在ruby​​mine控制台中运行follwing命令时的错误，但在rakedb期间会发生同样的2for1错误:种子):MODEL1.all.sample和MODEL1.all我明白了:DealerLoad(0.3ms)SELECT"MODEL1".*FROM"MODEL1S"ArgumentError:wrongnumberofarguments(2for1)from/

随机推荐