"Damn Single (单身狗)" is the Chinese nickname for someone who is being single. You are supposed to find those who are alone in a big party, so they can be taken care of.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 50,000), the total number of couples. Then N lines of the couples follow, each gives a couple of ID's which are 5-digit numbers (i.e. from 00000 to 99999). After the list of couples, there is a positive integer M (≤ 10,000) followed by M ID's of the party guests. The numbers are separated by spaces. It is guaranteed that nobody is having bigamous marriage (重婚) or dangling with more than one companion.
Output Specification:
First print in a line the total number of lonely guests. Then in the next line, print their ID's in increasing order. The numbers must be separated by exactly 1 space, and there must be no extra space at the end of the line.
Sample Input:
3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333
Sample Output:
5
10000 23333 44444 55555 88888
题目大意:给出N对情侣,然后在M个客人中找出单身狗并且按照名字的字母升序排列输出。。。
思路:用unordered_map存储每对情侣,用unordered_set存储客人信息,遍历客人的集合,如果当前的ID没有对象或者他的对象没有参加party,那么就属于单身狗。(另一半没来的也是单身狗!!!)
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;
unordered_map <string, string> cp;
unordered_set <string> guest;
bool isSingle(string ID);
int main()
{
int N, M, i;
vector <string> ans;
scanf("%d", &N);
for (i = 0; i < N; i++) {
string v, u;
cin >> v >> u;
cp[v] = u;
cp[u] = v;
}
scanf("%d", &M);
for (i = 0; i < M; i++) {
string ID;
cin >> ID;
guest.insert(ID);
}
for (auto it = guest.begin(); it != guest.end(); it++)
if (isSingle(*it))
ans.push_back(*it);
sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for (i = 0; i < ans.size(); i++) {
printf("%s", ans[i].c_str());
if (i < ans.size() - 1)
printf(" ");
}
}
bool isSingle(string ID) {
if (guest.find(cp[ID]) == guest.end())
return true;
else
return false;
}