PAT_A1121#Damn Single

Source:

PAT A1121?Damn Single?(25?分)

Description:

"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
22222 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 22222 23333

Sample Output:

5
10000 23333 44444 55555 88888

Keys:

• 哈希映射

Code:

 1 /*
 2 Data: 2019-07-19 18:24:58
 3 Problem: PAT_A1121#Damn Single
 4 AC: 13:30
 5 
 6 题目大意：
 7 找出独自前往派对的人
 8 输入：
 9 第一行给出，伴侣数N<=5e4（意味着最多1e5个人）
10 接下来N行，p1,p2
11 接下来一行，出席人数M<=1e4
12 接下来一行，给出M个id(5位)
13 输出：
14 独自参加派对的人数
15 id递增
16 
17 基本思路：
18 有一点需要注意下，id值可能为0，因此哈希表的初始值置-1就可以了；
19 */
20 
21 #include<cstdio>
22 #include<vector>
23 #include<algorithm>
24 using namespace std;
25 const int M=1e6;
26 vector<int> attend,single;
27 int cp[M],mp[M]={0};
28 
29 int main()
30 {
31 #ifdef    ONLINE_JUDGE
32 #else
33     freopen("Test.txt","r",stdin);
34 #endif
35 
36     fill(mp,mp+M,-1);
37     int n,p1,p2;
38     scanf("%d",&n);
39     for(int i=0; i<n; i++)
40     {
41         scanf("%d%d",&p1,&p2);
42         cp[p1]=p2;
43         cp[p2]=p1;
44         mp[p1]=mp[p2]=1;
45     }
46     scanf("%d",&n);
47     for(int i=0; i<n; i++)
48     {
49         scanf("%d",&p1);
50         attend.push_back(p1);
51         if(mp[p1]==0)
52             mp[p1]=mp[cp[p1]]=1;
53         else
54             mp[p1]=mp[cp[p1]]=0;
55     }
56     for(int i=0; i<n; i++)
57         if(mp[attend[i]]==0)
58             single.push_back(attend[i]);
59     sort(single.begin(),single.end());
60     printf("%dn",single.size());
61     for(int i=0; i<single.size(); i++)
62         printf("%05d%c",single[i],i==single.size()-1?‘n‘:‘ ‘);
63 
64     return 0;
65 }

?

?

?

?

"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,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,and there must be no extra space at the end of the line.

Sample Input:

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

Sample Output:

5
10000 23333 44444 55555 88888