1065 单身狗

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。

输入格式：

输入第一行给出一个正整数 N（≤ 50 000），是已知夫妻/伴侣的对数；随后 N 行，每行给出一对夫妻/伴侣——为方便起见，每人对应一个 ID 号，为 5 位数字（从 00000 到 99999），ID 间以空格分隔；之后给出一个正整数 M（≤ 10 000），为参加派对的总人数；随后一行给出这 M 位客人的 ID，以空格分隔。题目保证无人重婚或脚踩两条船。

输出格式：

首先第一行输出落单客人的总人数；随后第二行按 ID 递增顺序列出落单的客人。ID 间用 1 个空格分隔，行的首尾不得有多余空格。

输入样例：

tex

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

输出样例：

tex

5
10000 23333 44444 55555 88888

5
10000 23333 44444 55555 88888

Solution：

WARNING

测试点 3、4 运行超时

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());
		Map<String, String> map = new HashMap<String, String>();
		for (int i = 0; i < n; i++) {
			String[] a = in.readLine().split(" ");
			map.put(a[0], a[1]);
			map.put(a[1], a[0]);
		}
		int m = Integer.parseInt(in.readLine());
		String[] a = in.readLine().split(" ");
		Set<String> set = new HashSet<>();
		List<String> result = new LinkedList<>();
		for (int i = 0; i < m; i++) {
			set.add(a[i]);
		}
		for (int i = 0; i < m; i++) {
			String x = map.get(a[i]);
			if (!set.contains(x)) {
				result.add(a[i]);
			}
		}
		map.clear();
		Collections.sort(result);
		StringBuilder sb = new StringBuilder();
		for (String s : result) {
			sb.append(s).append(" ");
		}
		System.out.printf("%d\n%s", result.size(), sb.toString().trim());
	}

}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());
		Map<String, String> map = new HashMap<String, String>();
		for (int i = 0; i < n; i++) {
			String[] a = in.readLine().split(" ");
			map.put(a[0], a[1]);
			map.put(a[1], a[0]);
		}
		int m = Integer.parseInt(in.readLine());
		String[] a = in.readLine().split(" ");
		Set<String> set = new HashSet<>();
		List<String> result = new LinkedList<>();
		for (int i = 0; i < m; i++) {
			set.add(a[i]);
		}
		for (int i = 0; i < m; i++) {
			String x = map.get(a[i]);
			if (!set.contains(x)) {
				result.add(a[i]);
			}
		}
		map.clear();
		Collections.sort(result);
		StringBuilder sb = new StringBuilder();
		for (String s : result) {
			sb.append(s).append(" ");
		}
		System.out.printf("%d\n%s", result.size(), sb.toString().trim());
	}

}

1065 单身狗 ​

输入格式： ​

输出格式： ​

输入样例： ​

输出样例： ​

Solution： ​