SG1. 火眼金睛
描述
现在我们需要查出一些作弊的问答社区中的ID，作弊有两种：1.A回答了B的问题，同时B回答了A的问题。那么A和B都是作弊。2.作弊ID用户A和作弊ID用户B同时回答了C的问题，那么C也是作弊。已知每个用户的ID是一串数字，一个问题可能有多个人回答。输入描述
每组数据第一行为总问题数N(N小于等于200000)，第二行开始每行一个问题，第一个数字为提问人ID，第二个数字为回答人数，后面则为所有回答人的ID。(ID均为0-1000000的整数)输出描述
第一行为作弊ID数量，第二行开始为从小到大的每行一个作弊ID。示例1
输入:
3 1 1 2 2 1 1 3 2 1 2
输出:
3 1 2 3
C++ 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2017-09-05
#if 1
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <math.h>
#include <string>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <time.h>
#include <iomanip>
typedef unsigned int uint;
using namespace std;
/*
题目描述
现在我们需要查出一些作弊的问答社区中的ID，作弊有两种：1.A回答了B的问题，同时B回答了A的问题。那么A和B都是作弊。
2.作弊ID用户A和作弊ID用户B同时回答了C的问题，那么C也是作弊。已知每个用户的ID是一串数字，一个问题可能有多个人回答。
输入描述:
每组数据第一行为总问题数N(N小于等于200000)，第二行开始每行一个问题，第一个数字为提问人ID，第二个数字为回答人数，
后面则为所有回答人的ID。(ID均为0-1000000的整数)
输出描述:
第一行为作弊ID数量，第二行开始为从小到大的每行一个作弊ID。
示例1
输入
3
1 1 2
2 1 1
3 2 1 2
输出
3
1 2 3
*/
int main()
{
int n;
int tempID;
while (cin >> n)
{
map<int, set<int> > map;
for (int i = 0; i < n; i ++)
{
int askId;
cin >> askId;
int num;
cin >> num;
//之前askId没有提问过
if (map.find(askId) == map.end())
{
set<int> tmpSet;
for (int j = 0; j < num; j ++)
{
int awserId;
cin >> awserId;
if (awserId != askId)
{
tmpSet.insert(awserId);
}
}
if (!tmpSet.empty()) {
map.insert(make_pair(askId, tmpSet));
}
}
//之前askId已经提问过
else
{
for (int j = 0; j < num; j ++)
{
int awserId;
cin >> awserId;
if (askId != awserId)
{
map[askId].insert(awserId);
}
}
}
}//for
set<int> resSet;
//相互提问回答的作弊者
for (auto it = map.begin(); it != map.end(); ++ it)
{
for (auto ite = it->second.begin(); ite != it->second.end(); ++ ite)
{
if (map.find(*ite) != map.end())
{
if (map[*ite].find(it->first) != map[*ite].end())
{
resSet.insert(it->first);
resSet.insert(*ite);
}
}
}
}
//两个相互提问回答作弊者的共同回答者
int sz = resSet.size();
while (true)
{
for (auto it = map.begin(); it != map.end(); ++ it)
{
int count = 0;
for (auto ite = it->second.begin(); ite != it->second.end(); ++ ite)
{
if (resSet.find(*ite) != resSet.end())
{
count ++;
}
}
if (count >= 2)
{
resSet.insert(it->first);
}
}
if (sz != resSet.size())
{
sz = resSet.size();
}
else break;
}
cout << resSet.size() << endl;
if (!resSet.empty())
{
bool first = true;
for (auto it = resSet.begin(); it != resSet.end(); ++it)
{
if (first)
{
cout << *it;
first = false;
}
else
{
cout << " " << *it;
}
}
cout << endl;
}
}
return 0;
}
#endif
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-10-31
#if 1
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <math.h>
#include <string>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <time.h>
#include <iomanip>
typedef unsigned int uint;
using namespace std;
/*
题目描述
现在我们需要查出一些作弊的问答社区中的ID，作弊有两种：1.A回答了B的问题，同时B回答了A的问题。那么A和B都是作弊。
2.作弊ID用户A和作弊ID用户B同时回答了C的问题，那么C也是作弊。已知每个用户的ID是一串数字，一个问题可能有多个人回答。
输入描述:
每组数据第一行为总问题数N(N小于等于200000)，第二行开始每行一个问题，第一个数字为提问人ID，第二个数字为回答人数，
后面则为所有回答人的ID。(ID均为0-1000000的整数)
输出描述:
第一行为作弊ID数量，第二行开始为从小到大的每行一个作弊ID。
示例1
输入
3
1 1 2
2 1 1
3 2 1 2
输出
3
1 2 3
*/
int main()
{
int n;
int tempID;
while (cin >> n)
{
map<int, set<int> > map;
for (int i = 0; i < n; i ++)
{
int askId;
cin >> askId;
int num;
cin >> num;
//之前askId没有提问过
if (map.find(askId) == map.end())
{
set<int> tmpSet;
for (int j = 0; j < num; j ++)
{
int awserId;
cin >> awserId;
if (awserId != askId)
{
tmpSet.insert(awserId);
}
}
if (!tmpSet.empty()) {
map.insert(make_pair(askId, tmpSet));
}
}
//之前askId已经提问过
else
{
for (int j = 0; j < num; j ++)
{
int awserId;
cin >> awserId;
if (askId != awserId)
{
map[askId].insert(awserId);
}
}
}
}//for
set<int> resSet;
//相互提问回答的作弊者
for (auto it = map.begin(); it != map.end(); ++ it)
{
for (auto ite = it->second.begin(); ite != it->second.end(); ++ ite)
{
if (map.find(*ite) != map.end())
{
if (map[*ite].find(it->first) != map[*ite].end())
{
resSet.insert(it->first);
resSet.insert(*ite);
}
}
}
}
//两个相互提问回答作弊者的共同回答者
int sz = resSet.size();
while (true)
{
for (auto it = map.begin(); it != map.end(); ++ it)
{
int count = 0;
for (auto ite = it->second.begin(); ite != it->second.end(); ++ ite)
{
if (resSet.find(*ite) != resSet.end())
{
count ++;
}
}
if (count >= 2)
{
resSet.insert(it->first);
}
}
if (sz != resSet.size())
{
sz = resSet.size();
}
else break;
}
cout << resSet.size() << endl;
if (!resSet.empty())
{
bool first = true;
for (auto it = resSet.begin(); it != resSet.end(); ++it)
{
if (first)
{
cout << *it;
first = false;
}
else
{
cout << " " << *it;
}
}
cout << endl;
}
}
return 0;
}
#endif
C++ 解法, 执行用时: 2ms, 内存消耗: 396KB, 提交时间: 2020-09-06
#if 1
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <math.h>
#include <string>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <time.h>
#include <iomanip>
typedef unsigned int uint;
using namespace std;
/*
题目描述
现在我们需要查出一些作弊的问答社区中的ID，作弊有两种：1.A回答了B的问题，同时B回答了A的问题。那么A和B都是作弊。
2.作弊ID用户A和作弊ID用户B同时回答了C的问题，那么C也是作弊。已知每个用户的ID是一串数字，一个问题可能有多个人回答。
输入描述:
每组数据第一行为总问题数N(N小于等于200000)，第二行开始每行一个问题，第一个数字为提问人ID，第二个数字为回答人数，
后面则为所有回答人的ID。(ID均为0-1000000的整数)
输出描述:
第一行为作弊ID数量，第二行开始为从小到大的每行一个作弊ID。
示例1
输入
3
1 1 2
2 1 1
3 2 1 2
输出
3
1 2 3
*/
int main()
{
int n;
int tempID;
while (cin >> n)
{
map<int, set<int> > map;
for (int i = 0; i < n; i ++)
{
int askId;
cin >> askId;
int num;
cin >> num;
//之前askId没有提问过
if (map.find(askId) == map.end())
{
set<int> tmpSet;
for (int j = 0; j < num; j ++)
{
int awserId;
cin >> awserId;
if (awserId != askId)
{
tmpSet.insert(awserId);
}
}
if (!tmpSet.empty()) {
map.insert(make_pair(askId, tmpSet));
}
}
//之前askId已经提问过
else
{
for (int j = 0; j < num; j ++)
{
int awserId;
cin >> awserId;
if (askId != awserId)
{
map[askId].insert(awserId);
}
}
}
}//for
set<int> resSet;
//相互提问回答的作弊者
for (auto it = map.begin(); it != map.end(); ++ it)
{
for (auto ite = it->second.begin(); ite != it->second.end(); ++ ite)
{
if (map.find(*ite) != map.end())
{
if (map[*ite].find(it->first) != map[*ite].end())
{
resSet.insert(it->first);
resSet.insert(*ite);
}
}
}
}
//两个相互提问回答作弊者的共同回答者
int sz = resSet.size();
while (true)
{
for (auto it = map.begin(); it != map.end(); ++ it)
{
int count = 0;
for (auto ite = it->second.begin(); ite != it->second.end(); ++ ite)
{
if (resSet.find(*ite) != resSet.end())
{
count ++;
}
}
if (count >= 2)
{
resSet.insert(it->first);
}
}
if (sz != resSet.size())
{
sz = resSet.size();
}
else break;
}
cout << resSet.size() << endl;
if (!resSet.empty())
{
bool first = true;
for (auto it = resSet.begin(); it != resSet.end(); ++it)
{
if (first)
{
cout << *it;
first = false;
}
else
{
cout << " " << *it;
}
}
cout << endl;
}
}
return 0;
}
#endif
C++ 解法, 执行用时: 2ms, 内存消耗: 416KB, 提交时间: 2021-09-07
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <math.h>
#include <string>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <time.h>
#include <iomanip>
typedef unsigned int uint;
using namespace std;
/*
题目描述
现在我们需要查出一些作弊的问答社区中的ID，作弊有两种：1.A回答了B的问题，同时B回答了A的问题。那么A和B都是作弊。
2.作弊ID用户A和作弊ID用户B同时回答了C的问题，那么C也是作弊。已知每个用户的ID是一串数字，一个问题可能有多个人回答。
输入描述:
每组数据第一行为总问题数N(N小于等于200000)，第二行开始每行一个问题，第一个数字为提问人ID，第二个数字为回答人数，
后面则为所有回答人的ID。(ID均为0-1000000的整数)
输出描述:
第一行为作弊ID数量，第二行开始为从小到大的每行一个作弊ID。
示例1
输入
3
1 1 2
2 1 1
3 2 1 2
输出
3
1 2 3
*/
int main()
{
int n;
int tempID;
while (cin >> n)
{
map<int, set<int> > map;
for (int i = 0; i < n; i ++)
{
int askId;
cin >> askId;
int num;
cin >> num;
//之前askId没有提问过
if (map.find(askId) == map.end())
{
set<int> tmpSet;
for (int j = 0; j < num; j ++)
{
int awserId;
cin >> awserId;
if (awserId != askId)
{
tmpSet.insert(awserId);
}
}
if (!tmpSet.empty()) {
map.insert(make_pair(askId, tmpSet));
}
}
//之前askId已经提问过
else
{
for (int j = 0; j < num; j ++)
{
int awserId;
cin >> awserId;
if (askId != awserId)
{
map[askId].insert(awserId);
}
}
}
}//for
set<int> resSet;
//相互提问回答的作弊者
for (auto it = map.begin(); it != map.end(); ++ it)
{
for (auto ite = it->second.begin(); ite != it->second.end(); ++ ite)
{
if (map.find(*ite) != map.end())
{
if (map[*ite].find(it->first) != map[*ite].end())
{
resSet.insert(it->first);
resSet.insert(*ite);
}
}
}
}
//两个相互提问回答作弊者的共同回答者
int sz = resSet.size();
while (true)
{
for (auto it = map.begin(); it != map.end(); ++ it)
{
int count = 0;
for (auto ite = it->second.begin(); ite != it->second.end(); ++ ite)
{
if (resSet.find(*ite) != resSet.end())
{
count ++;
}
}
if (count >= 2)
{
resSet.insert(it->first);
}
}
if (sz != resSet.size())
{
sz = resSet.size();
}
else break;
}
cout << resSet.size() << endl;
if (!resSet.empty())
{
bool first = true;
for (auto it = resSet.begin(); it != resSet.end(); ++it)
{
if (first)
{
cout << *it;
first = false;
}
else
{
cout << " " << *it;
}
}
cout << endl;
}
}
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2020-11-04
#if 1
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <math.h>
#include <string>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <time.h>
#include <iomanip>
typedef unsigned int uint;
using namespace std;
/*
题目描述
现在我们需要查出一些作弊的问答社区中的ID，作弊有两种：1.A回答了B的问题，同时B回答了A的问题。那么A和B都是作弊。
2.作弊ID用户A和作弊ID用户B同时回答了C的问题，那么C也是作弊。已知每个用户的ID是一串数字，一个问题可能有多个人回答。
输入描述:
每组数据第一行为总问题数N(N小于等于200000)，第二行开始每行一个问题，第一个数字为提问人ID，第二个数字为回答人数，
后面则为所有回答人的ID。(ID均为0-1000000的整数)
输出描述:
第一行为作弊ID数量，第二行开始为从小到大的每行一个作弊ID。
示例1
输入
3
1 1 2
2 1 1
3 2 1 2
输出
3
1 2 3
*/
int main()
{
int n;
int tempID;
while (cin >> n)
{
map<int, set<int> > map;
for (int i = 0; i < n; i ++)
{
int askId;
cin >> askId;
int num;
cin >> num;
//之前askId没有提问过
if (map.find(askId) == map.end())
{
set<int> tmpSet;
for (int j = 0; j < num; j ++)
{
int awserId;
cin >> awserId;
if (awserId != askId)
{
tmpSet.insert(awserId);
}
}
if (!tmpSet.empty()) {
map.insert(make_pair(askId, tmpSet));
}
}
//之前askId已经提问过
else
{
for (int j = 0; j < num; j ++)
{
int awserId;
cin >> awserId;
if (askId != awserId)
{
map[askId].insert(awserId);
}
}
}
}//for
set<int> resSet;
//相互提问回答的作弊者
for (auto it = map.begin(); it != map.end(); ++ it)
{
for (auto ite = it->second.begin(); ite != it->second.end(); ++ ite)
{
if (map.find(*ite) != map.end())
{
if (map[*ite].find(it->first) != map[*ite].end())
{
resSet.insert(it->first);
resSet.insert(*ite);
}
}
}
}
//两个相互提问回答作弊者的共同回答者
int sz = resSet.size();
while (true)
{
for (auto it = map.begin(); it != map.end(); ++ it)
{
int count = 0;
for (auto ite = it->second.begin(); ite != it->second.end(); ++ ite)
{
if (resSet.find(*ite) != resSet.end())
{
count ++;
}
}
if (count >= 2)
{
resSet.insert(it->first);
}
}
if (sz != resSet.size())
{
sz = resSet.size();
}
else break;
}
cout << resSet.size() << endl;
if (!resSet.empty())
{
bool first = true;
for (auto it = resSet.begin(); it != resSet.end(); ++it)
{
if (first)
{
cout << *it;
first = false;
}
else
{
cout << " " << *it;
}
}
cout << endl;
}
}
return 0;
}
#endif