單身狗”是中文對于單身人士的一種愛稱。本題請你從上萬人的大型派對中找出落單的客人，以便給予特殊關愛。
輸入格式：
輸入第一行給出一個正整數 N（≤?50 000），是已知夫妻/伴侶的對數；隨后 N 行，每行給出一對夫妻/伴侶——為方便起見，每人對應一個 ID 號，為 5 位數字（從 00000 到 99999），ID 間以空格分隔；之后給出一個正整數 M（≤?10 000），為參加派對的總人數；隨后一行給出這 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 //一個bool數組來表示是否是單身狗 //如果spouse[id] == 0 代表一定是單身狗 //否則，bool[id] 先改成true //如果bool[spouse[id]]為true，說明對象已經有了，就把cnt--，并且把它改為false //第三個測試點過不去，可能會某個值出現了兩次，問題真是存疑 #include<cstdio>const int maxn = 100000; int spouse[maxn] = {0}; bool isDog[maxn] = {false}; int arr[maxn];int main(){int n,m;scanf("%d",&n);int g,b;for(int i = 0; i < n; i++){scanf("%d %d",&g,&b);spouse[g] = b;spouse[b] = g;}scanf("%d",&m);int cnt = 0;for(int i = 0; i < m; i++){scanf("%d",&b);if(!spouse[b]){ // 沒有對象isDog[b] = true;cnt++;}else{ // 有對象 if(isDog[spouse[b]]){ //對象在 isDog[spouse[b]] = false;//isDog[b] = false;cnt--;}else{ //對象不在 isDog[b] = true;cnt++;}}} //printf("%d",isDog[22156]);printf("%d\n",cnt);for(int i = 0; i < maxn; i++){if(isDog[i]) {printf("%05d%c",i,--cnt ? ' ' : '\0');//if(--cnt) printf(" "); } } // printf("%d",cnt);return 0; }
//第二個測試點過不去 #include<cstdio> const int maxn = 100000; int spouse[maxn] = {0}; int main(){int n;int u,v;scanf("%d",&n);for(int i = 0; i < n; i++){scanf("%d%d",&u,&v);spouse[u] = v;spouse[v] = u;}scanf("%d",&n);int cnt = 0;for(int i = 0; i < n; i++){scanf("%d",&u);if(!spouse[u]) spouse[u] = -1,cnt++;else spouse[u] = -2;}for(int i = 0; i < maxn; i++){if(spouse[i] > 0 && spouse[spouse[i]] == -2){spouse[spouse[i]] = -1;cnt++;}}printf("%d\n",cnt);for(int i = 0; i < maxn; i++){if(spouse[i] == -1) printf("%05d%c", i, --cnt ? ' ' : '\0');}return 0; }
//網友的答案 #include<cstdio> const int maxn = 100000; int spouse[maxn] = {0}; #define BLANK -1 #define SINGED -2 #define SINGLE -3 int main(){int n;int u,v;for(int i = 0 ; i < maxn; i++) spouse[i] = BLANK;scanf("%d",&n);for(int i = 0; i < n; i++){scanf("%d%d",&u,&v);spouse[u] = v;spouse[v] = u;}scanf("%d",&n);int cnt = 0;for(int i = 0; i < n; i++){scanf("%d",&u);if(spouse[u] >= 0) spouse[u] = SINGED;else spouse[u] = SINGLE,cnt++;}for(int i = 0; i < maxn; i++){if(spouse[i] >= 0 && spouse[spouse[i]] == SINGED){spouse[spouse[i]] = SINGLE;cnt++;}}printf("%d\n",cnt);for(int i = 0; i < maxn; i++){if(spouse[i] == SINGLE) printf("%05d%c", i, --cnt ? ' ' : '\0');}return 0; }
?
