pta单身狗

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

输入格式：

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

输出格式：

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

输入样例：

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

输出样例：

5
10000 23333 44444 55555 88888

?问题思路分析：

由于伴侣的ID号在00000到99999中，所以设一个大数组a来存储每个人的伴侣信息，初始化赋值为0，将情侣中的数据都存入该数组。当输入的情侣数为0的时候，我们就那么就是说不存在情侣，也就是说后面给出的M位客人就都是单身狗，按ID排序后直接输出。

值得注意的是对伴侣没有来的也算是落单的，所以我们就另外设一个数组c来记录状态，初始值为0，将M位客人加入，每次将该客人和他的伴侣一起加一。到最后遍历一下M位客人在该数组代表的值，如果为一就代表客人落单了，记录，最后将记录的按ID排序打印。

代码展示：

#include<bits/stdc++.h>
using namespace std;
map<int,int>t;
int main(){
   int n;
    scanf("%d",&n);
    int a[100000]={0};
    for(int i=0;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x]=y;
        a[y]=x;
    }
    int m;
    scanf("%d",&m);
    int b[m];
    int c[100000]={0};
    for(int i=0;i<m;i++){
        scanf("%d",&b[i]);
        c[b[i]]++;c[a[b[i]]]++;
    }
    if(n==0){
        sort(b,b+m);
        for(int i=0;i<m;i++){
        printf("%05d",b[i]);
        if(i!=m-1)printf(" ");
        else printf("\n");
    }
    }
    int d[m];
    int k=0;
    for(int i=0;i<m;i++){
        if(c[b[i]]==1)d[k++]=b[i];
    }
    sort(d,d+k);
    printf("%d\n",k);
    for(int i=0;i<k;i++){
        printf("%05d",d[i]);
        if(i!=k-1)printf(" ");
        else printf("\n");
    }
}

复杂度分析：

代码的时间复杂度为 O(n + mlogm + klogk)，其中 n 是已知夫妻/伴侣的对数，m 是参加派对的总人数，k 是落单客人的数量。空间复杂度为 O(n + m + k)，主要是用于存储夫妻/伴侣关系的 map 和数组的空间。