题解 | #火眼金睛# 集合、哈希表

这题的输入输出、测试用例都挺恶心的，每个题竟然可以自问自答，也可以重复由同一个人回答，因此用集合方便去重

思路大体不难，但细思还挺绕，需要熟悉哈希表中嵌套集合的遍历语法

#include <iostream>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int main() {
    int N;
    while (cin >> N) {
        unordered_map<int, unordered_set<int>>aq; // 谁回答了什么问题
        unordered_map<int, set<int>>qa; // 每个问题由谁来回答
        while (N--) {
            int qID, aNum;
            cin >> qID >> aNum;
            while (aNum--) {
                int aID;
                cin >> aID;
                aq[aID].insert(qID);
                qa[qID].insert(aID);
            }
        }
        set<int> cheater; // 存储作弊者ID
        // 遍历结构【谁回答了什么问题】中的元素，验证A回答了B的问题，同时B回答了A的问题
        for (auto iter = aq.begin(); iter != aq.end(); iter++) {
            for (auto iter2 = next(iter); iter2 != aq.end(); iter2++) {
                if (iter->second.find(iter2->first) != iter->second.end() &&
                        iter2->second.find(iter->first) != iter2->second.end()) {
                    cheater.insert(iter->first);
                    cheater.insert(iter2->first);
                }
            }
        }
        // 遍历结构【每个问题由谁来回答】中的元素，如果某问题的回答者都是作弊者，那么他也是作弊者
        for (auto& iter : qa) {
            if (iter.second == cheater) {
                cheater.insert(iter.first);
            }
        }
        cout << cheater.size() << endl;
        for (auto& iter : cheater) {
            cout << iter << " ";
        }
        if (cheater.size() != 0) {
            cout << endl;
        }
    }
    return 0;
}

时间复杂度：O(N*M)，N为问题数量，M为回答者数量

空间复杂度：O(N+M)，用于存储两个哈希表