1000ms

Difficulty: 4

所属公司 : 京东

时间 :2025年7月26日

算法与标签>模拟

会员或题库专享

请先，开通会员或购买题库京东机考编程题库，可解锁完整内容。

购买京东机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（京东机考编程题库），可解锁完整内容。

购买题库开通会员

题解思路与方法

问题重述

给定一个无向图 $G$ ，定义边集 $X$ 为独立匹配，需同时满足：

匹配性： $X$ 中任意两条边不共享端点。
独立性：对于任意一条不在 $X$ 中的边，它最多与 $X$ 中的边共享一个端点（即不存在一条未选边与 $X$ 中的两条边分别在两个端点处相连）。

题目内容

在一个无向图 $G$ 中，独立匹配是图中的一个边集 $X$ ，满足任何一条不属于 $X$ 的边至多与 $X$ 中的边共享一个端点，且 $X$ 中任意两条边不共享端点。现在给出一个无向图和其中的一些边集，请你判断这些边集中哪一些是独立匹配。