[PAT-A] 1121 Damn Single

Java

测试点3、4超时

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 读取配偶对数量
        int n = Integer.parseInt(br.readLine());

        // 存储配偶对
        int[][] couples = new int[n][2];
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            couples[i][0] = Integer.parseInt(line[0]);
            couples[i][1] = Integer.parseInt(line[1]);
        }

        // 读取派对参与者数量和ID
        int m = Integer.parseInt(br.readLine());
        String[] guests = br.readLine().split(" ");
        Set<Integer> party = new HashSet<>();
        for (int i = 0; i < m; i++) {
            party.add(Integer.parseInt(guests[i]));
        }

        // 移除成对出现的配偶
        for (int[] couple : couples) {
            if (party.contains(couple[0]) && party.contains(couple[1])) {
                party.remove(couple[0]);
                party.remove(couple[1]);
            }
        }

        // 将剩余的单身人士排序
        Integer[] result = party.toArray(new Integer[0]);
        Arrays.sort(result);

        // 输出结果
        StringBuilder sb = new StringBuilder();
        sb.append(result.length).append('\n');

        for (int i = 0; i < result.length; i++) {
            if (i > 0) {
                sb.append(' ');
            }
            sb.append(String.format("%05d", result[i]));
        }
        System.out.print(sb);

        br.close();
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;

int n, m, k;
bool g[N][N];
int seq[N], cnt[N];

bool check() {
    if (seq[0] != seq[k - 1]) return false;

    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < k - 1; ++i) {
        if (!g[seq[i]][seq[i + 1]]) return false;
        cnt[seq[i]]++;
    }

    for (int i = 1; i <= n; ++i)
        if (cnt[i] != 1) return false;

    return true;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = g[b][a] = true;
    }

    int Q;
    scanf("%d", &Q);
    while (Q--) {
        scanf("%d", &k);
        for (int i = 0; i < k; ++i) scanf("%d", &seq[i]);

        if (check()) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}