解题思路

• 按题意从 f₁ 到 fₙ 依次处理：对每个前端的偏好列表，从高到低找第一个尚未被占用的后端并占用之；若整份清单都被占了，则无法全匹配。

• 这就是对题目给定贪心过程的直接模拟，无需额外的稳定性或最大匹配算法。

• 实现要点：

  • 用大小为 n+1 的布尔数组 used 标记后端是否已被占用。
  • 对第 i 个前端的 k 个候选后端按序检查，遇到未占用则标记并继续处理下一个前端；若都占用则直接判定本组数据为 NO（但仍需把输入读完）。
  • 因为总输入规模满足 ∑k < 1e6，顺序扫描即可。

复杂度分析

• 时间复杂度：对每个候选仅访问一次，整体为 O(∑k)。
• 空间复杂度：仅 used 数组，O(n)。

代码实现

Python

# 题意模拟 + 贪心
# 读取输入，按顺序为每个前端找到首个未被占用的后端即可

import sys

def can_match(n, prefs):
    used = [False] * (n + 1)  # 标记后端是否被占用
    for lst in prefs:
        ok = False
        for b in lst:         # 按优先级从高到低扫描
            if not used[b]:
                used[b] = True
                ok = True
                break
        if not ok:
            return False
    return True

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    T = next(it)
    out_lines = []
    for _ in range(T):
        n = next(it)
        prefs = []
        for _ in range(n):
            k = next(it)
            cur = [next(it) for _ in range(k)]
            prefs.append(cur)
        out_lines.append("YES" if can_match(n, prefs) else "NO")
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// 题意模拟 + 贪心
// 为每个前端按序找第一个未被占用的后端；使用布尔数组标记占用
import java.io.*;
import java.util.*;

public class Main {
    // 简单高效的整型输入读取（根据数据范围使用）
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= 32); // 跳过空白
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    // 按题意贪心判断能否全匹配
    static boolean canMatch(int n, FastScanner fs) throws IOException {
        boolean[] used = new boolean[n + 1]; // used[b] 表示后端 b 是否被占用
        for (int i = 0; i < n; i++) {
            int k = fs.nextInt();            // 该前端的清单长度
            boolean ok = false;              // 是否为该前端找到可用后端
            for (int j = 0; j < k; j++) {
                int b = fs.nextInt();
                if (!ok) {                   // 只在尚未匹配成功时尝试占用
                    if (!used[b]) {
                        used[b] = true;
                        ok = true;
                    }
                }
                // 若已 ok，仍需把本行剩余输入读完（已在上面继续循环）
            }
            if (!ok) return false;           // 此前端无法匹配，整组数据失败
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder sb = new StringBuilder();
        int T = fs.nextInt();
        for (int t = 0; t < T; t++) {
            int n = fs.nextInt();
            boolean ok = canMatch(n, fs);
            sb.append(ok ? "YES" : "NO").append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// 题意模拟 + 贪心
// 从 f1 到 fn，按优先级为每个前端找第一个未被占用的后端
#include <bits/stdc++.h>
using namespace std;

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

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; 
        cin >> n;
        vector<char> used(n + 1, 0); // used[b] = 1 表示后端 b 已被占用
        bool all_ok = true;
        for (int i = 0; i < n; ++i) {
            int k; 
            cin >> k;
            bool ok = false;         // 当前前端是否找到可用后端
            for (int j = 0; j < k; ++j) {
                int b; 
                cin >> b;
                if (!ok && !used[b]) {
                    used[b] = 1;
                    ok = true;
                }
                // 若已 ok，仍需把输入读完
            }
            if (!ok) all_ok = false; // 标记失败，但需把整组数据读完
        }
        cout << (all_ok ? "YES" : "NO") << "\n";
    }
    return 0;
}

题目内容

现有 $n$ 个前端工程师 $f_1,f_2,f_3,...,f_n$ 和 $n$ 个后端工程师 $b_1,b_2,..., b_n$ .

每个前端工程师都有一份想要合作的后端工程师清单,清单按照想要合作的优先级从高到低给出,并且每位后端工程师只能与一位前端工程师合作.

多多在构思合作方案,打算依次处理 ,,九,..,,前端的合作清单,并且对于每个清单按优先级从高到低寻找可合作的后端,如果找到的后端还没有合作对象,那么他们将达成合作关系.请问如果按照上述方案,使得每位前端工程师都能成功匹配到后端工程师的话,输出"YES”,否则输出"NO"(均不包含双引号)

输入描述

第一行,包含一个正整数 $T(1 ≤T≤ 10)$ 代表测试数据的组数

对于每组测试数据,分别有 $n+1$ 行

第一行,仅有一个正整数 $n(1 ≤n≤ 10^4)$

接下来 $n$ 行,每行先给出一个正整数 $k(1 ≤k≤ n)$ 代表此前端工程师的合作清单中后端工程师的数量.

接下来给出 $k$ 个不同的正整数,分别代表按优先级从高到低给出的后端工程师的编号 $b_i(1 ≤ b_i≤ n)$

保证每组数据中 $k$ 的总和小于 $10^6$

输出描述

对于每组数据,仅输出一行.

如果按照上述方案,可以全部匹配的话,输出 "$YES$”，否则输出 "$NO$" (均不包含双引号).

样例1

输入

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

输出

YES
NO
NO

说明

对于第一组数据:

前端 $f_1$ 按顺序从左到右匹配到后端 $b_2$

前端 $f_2$ 按顺序从左到右匹配到后端 $b_1$

前端 $f_3$ 按顺序从左到右匹配到后端 $b_3$

前端 $f_4$ 按顺序从左到右匹配到后端 $b_4$

可以完全匹配,输出 $YES$ .

对于第二组数据:

前端 $f_1$ 按顺序从左到右匹配到后端 $b_1$

前端 , 没有匹配到后端,不能完全匹配,输出 $NO$ .

对于第三组数据:

前端 $f_1$ 按顺序从左到右匹配到后端 $b_2$

前端 $f_2$ 没有匹配到后端不能完全匹配,输出 $NO$ .