题解思路与方法

问题重述

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

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

每个查询给出一组边编号，判断该边集是否满足上述两条性质。

算法流程

1. 读取边列表：用数组 edge[i] = (u_i, v_i) 存储第 $i$ 条边的两个端点。

2. 遍历每个查询：

   • 记查询边集大小为 $c$，边编号集合为 $S$。

   • 匹配性检查：

     • 用数组 used[v] 标记顶点 $v$ 是否已被 $X$ 中的某条边占用。遍历 $S$ 中的每条边 $(u,v)$：

       • 若 used[u] 或 used[v] 已为 true，则有共享端点，直接判 “No”。
       • 否则将 used[u]=used[v]=true。

   • 独立性检查（仅在匹配性通过后进行）：

     • 对所有边编号 $i\notin S$，令 $(u,v)=\text{edge}[i]$。若 used[u] && used[v]，说明该非选边与 $X$ 中的两条边共享了两个端点，判 “No”。

   • 若两步均未触发冲突，则判 “Yes”。

复杂度分析

• 每个查询匹配性检查花费 $O(c)$，独立性检查花费 $O(m)$。
• 共 $q$ 次查询，总时间 $O\bigl(\sum c + q\cdot m\bigr)\le O(qm + \sum c)$。
• 由于 $m\le2000,\ q\le30$，最坏约 $6\times10^4$ 次边扫描，极其高效。

代码实现

Python

import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    u_list = list(map(int, input().split()))
    v_list = list(map(int, input().split()))
    # 存储所有边
    edges = [(u_list[i], v_list[i]) for i in range(m)]

    q = int(input())
    for _ in range(q):
        data = list(map(int, input().split()))
        c = data[0]
        S = set(data[1:])  # 查询的边编号集合（1-based）

        used = [False] * (n + 1)  # 顶点占用标记

        ok = True
        # 匹配性检查
        for idx in S:
            u, v = edges[idx - 1]
            if used[u] or used[v]:
                ok = False
                break
            used[u] = used[v] = True

        # 独立性检查
        if ok:
            for i in range(1, m + 1):
                if i in S:
                    continue
                u, v = edges[i - 1]
                if used[u] and used[v]:
                    ok = False
                    break

        print("Yes" if ok else "No")

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 读取边端点
        int[] u = new int[m], v = new int[m];
        st = new StringTokenizer(in.readLine());
        for (int i = 0; i < m; i++) u[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(in.readLine());
        for (int i = 0; i < m; i++) v[i] = Integer.parseInt(st.nextToken());

        int q = Integer.parseInt(in.readLine());
        while (q-- > 0) {
            st = new StringTokenizer(in.readLine());
            int c = Integer.parseInt(st.nextToken());
            // 用 HashSet 存查询边编号
            Set<Integer> S = new HashSet<>();
            for (int i = 0; i < c; i++) {
                S.add(Integer.parseInt(st.nextToken()));
            }

            boolean[] used = new boolean[n + 1];
            boolean ok = true;
            // 匹配性检查
            for (int idx : S) {
                int uu = u[idx - 1], vv = v[idx - 1];
                if (used[uu] || used[vv]) {
                    ok = false;
                    break;
                }
                used[uu] = used[vv] = true;
            }
            // 独立性检查
            if (ok) {
                for (int i = 1; i <= m; i++) {
                    if (S.contains(i)) continue;
                    int uu = u[i - 1], vv = v[i - 1];
                    if (used[uu] && used[vv]) {
                        ok = false;
                        break;
                    }
                }
            }
            System.out.println(ok ? "Yes" : "No");
        }
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m);
    // 读入两行，分别是所有边的第一端点和第二端点
    for(int i = 0; i < m; i++) cin >> u[i];
    for(int i = 0; i < m; i++) cin >> v[i];

    int q;
    cin >> q;
    while(q--){
        int c;
        cin >> c;
        vector<bool> sel(m+1,false);
        for(int i = 0, idx; i < c; i++){
            cin >> idx;
            sel[idx] = true;  // 标记查询的边
        }

        vector<bool> used(n+1,false);
        bool ok = true;
        // 匹配性检查
        for(int i = 1; i <= m && ok; i++){
            if(!sel[i]) continue;
            int uu = u[i-1], vv = v[i-1];
            if(used[uu] || used[vv]){
                ok = false;
                break;
            }
            used[uu] = used[vv] = true;
        }
        // 独立性检查
        if(ok){
            for(int i = 1; i <= m; i++){
                if(sel[i]) continue;
                int uu = u[i-1], vv = v[i-1];
                if(used[uu] && used[vv]){
                    ok = false;
                    break;
                }
            }
        }

        cout << (ok ? "Yes\n" : "No\n");
    }

    return 0;
}

题目内容

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

输入描述

第一行有两个正整数 $n,m(1<=n<=1000,1<=m<=2000)$ ，代表图中的点数和边数。

接下来的两行给出了一个 $2*m$ 的矩阵，矩阵中的每一列都代表图中的一条边的两个端点。

保证图中没有自环，即不存在一条边其两个端点相同。

接下来的一行中有一个正整数 $q(1<=q<=30)$ ，代表询问的边集个数。

接下来 $q$ 行，每行开头有一个正整数 $c$ ，代表询问的边集大小，然后是 $c$ 个 $1$ 到 $m$ 之间的正整数(含 $1$ 和 $m$ )，代表询问的边集中边的编号。

数字间两两有空格隔开。

输出描述

对于每个边集，若该边集是一个独立匹配，则输出 $Yes$ 。否则输出 $No$ 。

样例1

输入

6 6
1 2 3 4 5 6
2 3 4 5 6 1
3
2 1 2
2 2 4
2 3 6

输出

No
No
Yes