[PAT-A] 1134 Vertex Cover

Java

测试点2、3超时

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    static class Edge {
        int a, b;

        Edge(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

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

        Edge[] edges = new Edge[m];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(reader.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(a, b);
        }

        int Q = Integer.parseInt(reader.readLine());
        while (Q-- > 0) {
            HashSet<Integer> vertices = new HashSet<>();

            st = new StringTokenizer(reader.readLine());
            int num = Integer.parseInt(st.nextToken());
            for (int i = 0; i < num; i++) {
                vertices.add(Integer.parseInt(st.nextToken()));
            }

            boolean success = true;
            for (int i = 0; i < m; i++) {
                if (!vertices.contains(edges[i].a) && !vertices.contains(edges[i].b)) {
                    success = false;
                    break;
                }
            }
            System.out.println(success ? "Yes" : "No");
        }
    }
}

C++

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

using namespace std;

const int N = 10010;

int n, m;
struct Edge {
    int a, b;
} e[N];
unordered_set<int> st;

int main() {
    scanf("%d%d", &n, &m);

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

    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int num;
        scanf("%d", &num);

        st.clear();
        for (int i = 0; i < num; ++i) {
            int x;
            scanf("%d", &x);
            st.insert(x);
        }

        bool success = true;
        for (int i = 0; i < m; ++i)
            if (!st.count(e[i].a) && !st.count(e[i].b)) {
                success = false;
                break;
            }

        if (success) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}