Kimi LeetCode 3910. 统计节点和为偶数的连通子图 Rust实现

发布时间:2026/8/15 11:13:40

Kimi    LeetCode 3910. 统计节点和为偶数的连通子图 Rust实现
这是 LeetCode 3910 的 Rust 实现题目要求统计节点和为偶数的连通诱导子图数量。思路由于 n \le 13可以枚举所有非空子集最多 2^{13}-1 8191 个对每个子集1. 计算节点值之和若为奇数则跳过2. 用 DFS/BFS 检查诱导子图是否连通使用位掩码表示子集高效判断连通性。rustimpl Solution {pub fn even_sum_subgraphs(nums: Veci32, edges: VecVeci32) - i32 {let n nums.len();let mut g: VecVecusize vec![vec![]; n];for e in edges {let u e[0] as usize;let v e[1] as usize;g[u].push(v);g[v].push(u);}let m (1usize n) - 1; // 全1掩码let mut ans 0;// 枚举所有非空子集 sub (1 ~ 2^n - 1)for sub in 1..m {// 1. 计算子集节点值之和let mut sum 0i32;for i in 0..n {if (sub i) 1 1 {sum nums[i];}}// 和为奇数跳过if sum % 2 ! 0 {continue;}// 2. 检查诱导子图是否连通// vis: 已访问标记。不在子集中的节点视为已访问let mut vis m ^ sub;// 从子集中任意一个节点开始DFSlet start sub.trailing_zeros() as usize;// DFS (迭代实现)let mut stack vec![start];vis | 1 start;while let Some(u) stack.pop() {for v in g[u] {if (vis v) 1 0 {vis | 1 v;stack.push(v);}}}// 如果所有位都是1说明子集内所有节点连通if vis m {ans 1;}}ans}}关键点要点 说明m (1usize n) - 1 n位全1掩码sub 枚举 从 1 到 2^n-1sum % 2 ! 0 快速排除奇数和子集vis m ^ sub 异或不在子集中的位设为1视为已访问sub.trailing_zeros() 找到最低位1的索引作为DFS起点vis m 所有位都为1说明子集中所有节点连通复杂度- 时间复杂度O(2^n \times (n m))其中 m 为边数- 空间复杂度O(n m)

相关新闻

一套可直接复用的 Codex AGENTS.md:全局规则与 Java 项目规则分层实践

一套可直接复用的 Codex AGENTS.md:全局规则与 Java 项目规则分层实践

2026/8/15 11:03:40

一套可直接复用的 Codex AGENTS.md:全局规则与 Java 项目规则分层实践 摘要:把跨项目行为放进全局规则,把可验证的技术、命令和交付约束放进项目规则,才能让 Codex 有执行力而不越权。 目录 文章目录一套可直接复用的 Codex AGENT…

DB板(download_board)的烧录及版本更新

DB板(download_board)的烧录及版本更新

2026/8/15 11:03:40

一、ITEEC_WinFlash的设置1.本司烧录常用SMB,故Connect_Mode选择Flash via DBGR/SMB2.Allocation为选择外部flash从哪里开始烧录,一般选择From Top(即就是从0开始);From Assigned 0x为自定义位置(填0也是从…

老Mac免费升级最新macOS终极指南:OpenCore Legacy Patcher 完整上手教程

老Mac免费升级最新macOS终极指南:OpenCore Legacy Patcher 完整上手教程

2026/8/15 11:03:40

老Mac免费升级最新macOS终极指南:OpenCore Legacy Patcher 完整上手教程 【免费下载链接】OpenCore-Legacy-Patcher Experience macOS just like before 项目地址: https://gitcode.com/GitHub_Trending/op/OpenCore-Legacy-Patcher 当屏幕弹出"此电脑无…

PyCharm安装配置全指南:从零搭建Python高效开发环境

PyCharm安装配置全指南:从零搭建Python高效开发环境

2026/8/15 12:03:42

1. 项目概述:为什么是PyCharm? 如果你刚开始学Python,或者从其他语言转过来,第一个要面对的问题往往不是语法,而是“用什么写代码”。记事本?太原始。IDLE?功能太弱。Visual Studio Code&#x…

开源智能眼镜怎么造?25元DIY方案把AI戴在脸上

开源智能眼镜怎么造?25元DIY方案把AI戴在脸上

2026/8/15 12:03:42

开源智能眼镜怎么造?25元DIY方案把AI戴在脸上 【免费下载链接】OpenGlass Turn any glasses into AI-powered smart glasses 项目地址: https://gitcode.com/GitHub_Trending/op/OpenGlass 一副能认出你面前陌生人、翻译路牌文字、随时帮你"看看这是什么…

虚拟主播翻唱音频处理全流程:从音源分离到母带制作实战指南

虚拟主播翻唱音频处理全流程:从音源分离到母带制作实战指南

2026/8/15 12:03:42

在实际的虚拟主播内容创作和数字娱乐领域,音频内容的二次创作与发布是一个高频需求。无论是虚拟主播(Vtuber)的直播切片、粉丝制作的二创翻唱,还是个人音乐爱好者的作品分享,都涉及到对原始音频素材的处理、剪辑、混音…

Windows与Office激活实战指南:KMS_VL_ALL_AIO如何一步到位搞定180天自动续期

Windows与Office激活实战指南:KMS_VL_ALL_AIO如何一步到位搞定180天自动续期

2026/8/15 12:03:42

Windows与Office激活实战指南:KMS_VL_ALL_AIO如何一步到位搞定180天自动续期 【免费下载链接】KMS_VL_ALL_AIO Smart Activation Script 项目地址: https://gitcode.com/gh_mirrors/km/KMS_VL_ALL_AIO 凌晨一点,小周刚装好系统,正准备…

免费离线OCR软件Umi-OCR零基础指南:截图、批量、PDF识别一次全搞定

免费离线OCR软件Umi-OCR零基础指南:截图、批量、PDF识别一次全搞定

2026/8/15 12:03:42

免费离线OCR软件Umi-OCR零基础指南:截图、批量、PDF识别一次全搞定 【免费下载链接】Umi-OCR OCR software, free and offline. 开源、免费的离线OCR软件。支持截屏/批量导入图片,PDF文档识别,排除水印/页眉页脚,扫描/生成二维码。…

网络直播:Agent时代,如何供给高质量数据?

网络直播:Agent时代,如何供给高质量数据?

2026/8/15 11:53:42

亮数据 Bright Data 第三季度线上直播 - 技术详解现场问答扫码预约直播,也可点击【阅读原文】进入报名网页。

比较好的亚太EMBA,问了6位校友师资差别真的挺大

比较好的亚太EMBA,问了6位校友师资差别真的挺大

2026/8/13 11:01:28

比较好的亚太EMBA核心差异先看什么?对于希望兼顾工作与系统管理能力提升的亚太区高管而言,筛选匹配度高的EMBA项目时,师资配置是决定学习体验与实际收获的核心要素之一。我们结合3-4个公开信息透明、办学历史较长的亚太区主流EMBA项目特点&am…

备考3个月对比6份资料 海外游学的亚洲EMBA面试注意点

备考3个月对比6份资料 海外游学的亚洲EMBA面试注意点

2026/8/14 10:48:24

备考海外游学的亚洲EMBA面试,核心要围绕项目国际化设计逻辑、个人跨文化管理经验匹配度两个维度准备,避免把游学模块等同于普通旅游参访的认知偏差。不少备考者花3个月对比6份资料,却容易忽略面试官对“国际视野落地能力”的考察——比如香港…

比较好的国内EMBA,问了二十位校友聊透人脉价值

比较好的国内EMBA,问了二十位校友聊透人脉价值

2026/8/13 17:17:06

比较好的国内EMBA核心差异体现在哪些方面?比较好的国内EMBA的核心长期价值,很大程度上依托于校友网络的连接质量与资源生态的活跃度,这也是不少高管在择校时优先考量的因素。我们结合3-4个市场关注度较高的项目公开信息,从课程、师…

一文读懂快消WMS怎么选?2026年国内外10大主流WMS品牌盘点

一文读懂快消WMS怎么选?2026年国内外10大主流WMS品牌盘点

2026/8/15 0:03:07

快消品(FMCG)是流通速度较快、竞争较为激烈的行业之一。一瓶饮料从出厂到消费者手中,往往只有几十天甚至几天的周转窗口。这决定了快消行业的仓储管理系统(WMS)与制造业、电商行业存在明显区别:它不仅需要管…

内景 空间站内部 中国空间站 太空 内仓

内景 空间站内部 中国空间站 太空 内仓

2026/8/15 0:03:07

本项目为前几天收费帮学妹做的一个项目,在工作环境中基本使用不到,但是很多学校把这个当作编程入门的项目来做,故分享出本项目供初学者参考。 一、项目描述 空间站内部 中国空间站 太空 内仓 地址:本地PC端运行(或Web…

重新定义数据接口:3个突破性场景让通达信数据读取更智能

重新定义数据接口:3个突破性场景让通达信数据读取更智能

2026/8/15 0:03:07

重新定义数据接口:3个突破性场景让通达信数据读取更智能 【免费下载链接】mootdx 通达信数据读取的一个简便使用封装 项目地址: https://gitcode.com/GitHub_Trending/mo/mootdx 当我们面对海量金融数据时,传统的数据获取方式往往让我们陷入困境—…

摆脱论文困扰!盘点2026年全网爆红的的AI论文写作工具

摆脱论文困扰!盘点2026年全网爆红的的AI论文写作工具

2026/8/15 1:04:46

一天写完毕业论文在2026年已不再是天方夜谭。2026年最炸裂、实测能大幅提速的AI论文写作工具,覆盖选题构思、文献整理、内容生成、格式排版等核心场景,真正帮你高效搞定论文难题。 一、全流程王者:一站式搞定论文全链路(一天定稿首…

导师推荐!2026最新AI论文工具测评与实用推荐

导师推荐!2026最新AI论文工具测评与实用推荐

2026/8/15 10:10:27

2026年真正好用的AI论文工具,核心看生成的论文质量、低AI味、格式正确、学术适配四大指标。综合实测,千笔AI、ThouPen、豆包、DeepSeek、Grammarly 是当前最值得推荐的梯队,覆盖从免费到付费、从中文到英文、从文科到理工的全场景需求。 一、…

告别游戏崩溃:XCOM 2模组管理器的智能革命

告别游戏崩溃:XCOM 2模组管理器的智能革命

2026/8/14 19:35:14

告别游戏崩溃:XCOM 2模组管理器的智能革命 【免费下载链接】xcom2-launcher The Alternative Mod Launcher (AML) is a replacement for the default game launchers from XCOM 2 and XCOM Chimera Squad. 项目地址: https://gitcode.com/gh_mirrors/xc/xcom2-lau…