Kimi LeetCode 3910. 统计节点和为偶数的连通子图 Java实现-北京尧图网络

这是 LeetCode 3910 的 Java 实现题目要求统计节点和为偶数的连通诱导子图数量。思路由于 n \le 13可以枚举所有非空子集最多 2^{13}-1 8191 个对每个子集1. 计算节点值之和若为奇数则跳过2. 用 DFS/BFS 检查诱导子图是否连通使用位掩码表示子集高效判断连通性。javaimport java.util.*;class Solution {private ListInteger[] g;private int vis;private int m;public int evenSumSubgraphs(int[] nums, int[][] edges) {int n nums.length;// 建图g new List[n];Arrays.setAll(g, k - new ArrayList());for (int[] e : edges) {g[e[0]].add(e[1]);g[e[1]].add(e[0]);}m (1 n) - 1; // 全1掩码表示所有节点都在已访问状态int ans 0;// 枚举所有非空子集 sub (1 ~ 2^n - 1)for (int sub 1; sub m; sub) {// 1. 计算子集节点值之和int sum 0;for (int i 0; i n; i) {if (((sub i) 1) 1) {sum nums[i];}}// 和为奇数跳过if (sum % 2 ! 0) {continue;}// 2. 检查诱导子图是否连通// vis: 已访问标记。初始时不在子集中的节点视为已访问m ^ sub// 这样DFS只会在子集内的节点中传播vis m ^ sub;// 从子集中任意一个节点开始DFS取最高位的1int start Integer.numberOfTrailingZeros(sub);dfs(start);// 如果所有位都是1说明子集内所有节点都被访问到即连通if (vis m) {ans;}}return ans;}private void dfs(int u) {vis | (1 u); // 标记u为已访问for (int v : g[u]) {// 如果v未被访问在子集中且未访问if (((vis v) 1) 0) {dfs(v);}}}}关键点解释要点说明m (1 n) - 1 n位全1掩码sub 枚举从 1 到 2^n-1每个整数代表一个子集sum % 2 ! 0 快速排除奇数和子集vis m ^ sub 异或不在子集中的位设为1视为已访问子集中的位为0待访问Integer.numberOfTrailingZeros(sub) 找到子集中最低位的1的位置作为DFS起点vis m DFS结束后所有位都为1说明子集中所有节点连通复杂度- 时间复杂度O(2^n \times (n m))其中 m 为边数- 空间复杂度O(n m)

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

相关推荐

人生代码 | 第4关：输入要节制 -- 节奏失控，努力白忙

深入骨髓！50行代码拆解LLM Harness工程：如何用“赛马机制”根治幻觉

iOS ATT框架深度解析：从IDFA权限管理到SKAdNetwork归因实战

更多资讯

学生信息管理系统实战：Servlet+JSP+MySQL课程设计源码解析

AI Agent工程化与编程工具实战：从API调用到多Agent协作

会议预约屏哪个品牌性价比高？2026年选型避坑指南

Flutter for OpenHarmony商城订单详情页开发实践与踩坑记录

Unity3D旋转地球从零搭建：贴图、材质、灯光与旋转脚本避坑详解

NE555单稳态电路从原理到实战：T=1.1RC公式推导与经典应用

今日更新

基于sEMG与IMU的手语手势识别：从数据采集到实时部署避坑指南

装配车间MES落地指南：SimpleMES工单流转、BOM与齐套检查实战

AI获客怎样减少重复线索？意客AI的原文复用与版本筛选

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？