现在我们需要查出一些作弊的问答社区中的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。
3 1 1 2 2 1 1 3 2 1 2
3 1 2 3
#include<iostream> #include<vector> #include<set> using namespace std; int main(){ int i,j,r,q,n,temp1,temp2;//问题数 while(cin >> n){ vector<vector<int> > p;//处理不均衡的数组有效 vector<int> pp; set<int> ppp;//自动去重排序 int s[1000000] = {0}; for(i=0;i<n;i++){ pp.clear(); cin >> temp1; pp.push_back(temp1); cin >> temp2; pp.push_back(temp2); for(j=0;j<temp2;j++){ cin >> temp1; pp.push_back(temp1); } p.push_back(pp); } for(i=0;i<p.size();i++){ int count = 0; for(j=2;j<p[i].size();j++){ int z = p[i][j]; if(s[z] == -1){//该问题说谎者人数 count++; } if(z == p[i][0])//自己回答自己则不在搜索 continue; for(q=i+1;q<p.size();q++){ if(p[q][0] == z){ for(r=2;r<p[q].size();r++){//该问题回答者的提问,该问题提问者是否也回答了,两者都有问题 if( p[q][r] == p[i][0] ){ s[p[i][0]] = -1;s[z] = -1; ppp.insert(p[i][0]); ppp.insert(z); break; } } } } } if(count >= 2){//超过两个的说谎者回答了该问题,故提问者作弊 s[p[i][0]] = -1; ppp.insert(p[i][0]); } } cout<<ppp.size()<<endl; int cc=0; for(auto it=ppp.begin();it!=ppp.end();it++){ if(++cc == ppp.size()) cout<<*it<<endl; else cout<<*it<<" "; } } }
#include <iostream> #include <stdio.h> #include <vector> #include <set> #include <map> using namespace std; int main(int argc, char** argv) { int N; while (scanf("%d", &N) != EOF) { map<int, set<int> > m; for (int i = 0; i < N; i++) { int askId; cin >> askId; int num; cin >> num; if (m.find(askId) == m.end()) { set<int> tmp; for (int j = 0; j < num; j++) { int awserId; cin >> awserId; if (awserId != askId) { tmp.insert(awserId); //cout << askId << ","<<awserId << " " << endl; } } if (!tmp.empty()) { m.insert(make_pair(askId, tmp)); } } else { for (int j = 0; j < num; j++) { int awserId; cin >> awserId; if (askId != awserId) { m[askId].insert(awserId); //cout << askId << "," << awserId << " " << endl; } } } } //cout << "size: " << m.size() << endl; set<int> res; for (auto it = m.begin(); it != m.end(); ++it) { for (auto ite = it->second.begin(); ite != it->second.end(); ++ite) { if (m.find(*ite) != m.end()) { if (m[*ite].find(it->first) != m[*ite].end()) { res.insert(it->first); res.insert(*ite); } } //cout << *ite << " "; } //cout << endl; } int sz = res.size(); while (1) { for (auto it = m.begin(); it != m.end(); ++it) { int count = 0; for (auto ite = it->second.begin(); ite != it->second.end(); ++ite) { if (res.find(*ite) != res.end()) { count++; } } if (count >= 2) { res.insert(it->first); } } if (sz != res.size()) { sz = res.size(); } else { break; } } cout << res.size() << endl; if (!res.empty()) { bool first = true; for (auto it = res.begin(); it != res.end();++it) { if(first) { cout<<*it; first = false; } else { cout <<" "<<*it; } } cout << endl; } } return 0; }
import java.util.*; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); while (input.hasNextLine()) { int n = Integer.parseInt(input.nextLine()); //每个出题者set Set<Long> lzs = new HashSet<>(n); //每个出题者的回答者set(去重,不包含自己) Map<Long, Set<Long>> qs = new HashMap<>(); for (int i = 0; i < n; i++) { String line = input.nextLine(); String[] all = line.split(" "); Long lz = Long.valueOf(all[0]); lzs.add(lz); Set<Long> set = qs.get(lz); if (set == null) { set = new HashSet<>(); qs.put(lz, set); } for (int j = 1; j < all.length; j++) { Long as = Long.valueOf(all[j]); if (as != lz) set.add(as); } } Set<Long> cheater = fun(lzs, qs); List<Long> list = new ArrayList<>(cheater); Collections.sort(list); System.out.println(list.size()); //如果个数为0,直接进行下个用例 if(list.size()==0) continue; for (int i = 0; i < list.size(); i++) { if (i > 0) System.out.print(" "); //数字间空格分开,最后一个后面不要空格 System.out.print(list.get(i)); } System.out.println();//换行 } } public static Set<Long> fun(Set<Long> lzs, Map<Long, Set<Long>> qs) { Set<Long> cheater = new HashSet<>(); //判断第一种情况作弊:互相回答问题 for (Long lz : lzs) { //对于每一个发问者lz ,找到回答他问题的回答者answers Set<Long> answers = qs.get(lz); if (answers != null) { for (Long answer : answers) { Set<Long> answerAsLz = qs.get(answer); if (answerAsLz != null && answerAsLz.contains(lz)) { //回答者的提问中是否有lz回答的问题 cheater.add(lz); cheater.add(answer); } } } } //第二种情况 boolean flag = false;//是否有新的作弊者加入 //当有新作弊者加入后要重新检查第二种作弊情况 do { flag = false; //对于每一个发问者lz for (Long lz : lzs) { //lz已经是作弊者,则跳过 if (cheater.contains(lz)) continue; //找到回答他问题的回答者answer Set<Long> answers = qs.get(lz); int times = 0; for (Long cheat : cheater) { if (answers.contains(cheat)) times++; //如果有两个作弊者回答了lz问题,则lz作弊 if (times >= 2) break; } if (times >= 2) { cheater.add(lz); flag = true;//有新作弊者加入 } } } while (flag); return cheater; } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner s=new Scanner(System.in); while(s.hasNext()){ int n=s.nextInt(); int[] a=new int[n]; int k=0; TreeSet<Integer> tl=new TreeSet<Integer>(); HashMap<Integer,HashSet<Integer>> hm=new HashMap<Integer,HashSet<Integer>>(); for(int i=0;i<n;i++){ int t=k++; a[t]=s.nextInt(); if(hm.get(a[t])==null){ HashSet<Integer> al=new HashSet<Integer>(); int num=s.nextInt(); for(int j=1;j<=num;j++){ al.add(s.nextInt()); } hm.put(a[t],al); }else{ int num=s.nextInt(); for(int j=1;j<=num;j++){ hm.get(a[i]).add(s.nextInt()); } } } //处理 for(int i=0;i<n;i++){ HashSet<Integer> al = hm.get(a[i]); for(int num:al){ if(hm.get(num)!=null){ if(a[i]!=num){ HashSet<Integer> al2=hm.get(num); for(int num2:al2){ if(num2==a[i]){ tl.add(num2); tl.add(a[i]); break; } } } } } } //处理2 for(int i=0;i<n;i++){ int count=0; HashSet<Integer> al = hm.get(a[i]); for(int num:al){ for(int num2:tl){ if(num==num2){ count++; } if(count>=2){ tl.add(a[i]); break; } } if(count>=2){ break; } } } System.out.println(tl.size()); for(int num2:tl){ System.out.println(num2); } } } }
// 先简单说明一下,题目要求ID范围是0-1000000,太大了,直接建立有向图会内存溢出。正确做法是将总人数归一化后建立有向图列表,最后输出时在映射会ID号。 // 这段程序我没有写,直接把数据定死成范围在1030内,最后也可以AC。特此说明。 #include <iostream> #include <vector> using namespace std; #define MaxNum 1030 int main() { int num; while (cin >> num) { vector<vector<int> > vv(MaxNum, vector<int>(MaxNum, -1)); vector<int> cheat(MaxNum, -1); int asker, n, tmp; int CheatNum = 0; // 建立有向图 while (num--) { cin >> asker >> n; for (int i = 0; i < n; i++) { cin >> tmp; vv[asker][tmp] = 1; } } // 遍历图,图中带有环的就是作弊者 for (int i = 0; i < MaxNum; i++) { for (int j = 0; j < MaxNum; j++) { if (i != j) { if (vv[i][j] == 1 && vv[j][i] == 1) { cheat[i] = 1; cheat[j] = 1; } } } } // 遍历图 更新作弊者列表,每行提问者的问题回答有两个以上作弊者的也是作弊者 // 感谢 @Sleepy小迪 现更新方法如下: // for (int i = 0; i < MaxNum; i++) { for (int i = 0; i < MaxNum;) { int cnt = 0; for (int j = 0; j < MaxNum; j++) { if (vv[i][j] == 1 && cheat[j] == 1) { cnt++; } } if (cnt > 1 && cheat[i] != 1) { cheat[i] = 1; i = 0; } else { ++i; } } for (int i = 0; i < MaxNum; i++) { if (cheat[i] == 1) { CheatNum++; } } cout << CheatNum << endl; for (int i = 0; i < MaxNum; i++) { if (cheat[i] == 1) { if (--CheatNum) { cout << i << " "; } else { cout << i << endl; } } } } return 0; }
//竟然可以AC了,说明:用户ID最大值不超过Nimport java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class Main45 { static List<Integer> getResult(int n,int[][] map) { ArrayList<Integer> list=new ArrayList<Integer>(); for(int i=0;i<=n;i++) { int cnt=0; for(int j=0;j<=n;j++) { if(map[i][j]==1 && map[j][i]==1 && i!=j) { if(!list.contains(i)) { list.add(i); cnt++; } } if(map[i][j]==1 && i!=j && list.contains(j)) cnt++; if(cnt>=2) { if(!list.contains(i)) { list.add(i); } } } } Collections.sort(list); return list; } public static void main(String[] args) { Scanner in=new Scanner(System.in); while(in.hasNext()) { /* n:问题个数 m[i]:提出问题i的人的编号 p[i]:回答问题i的人数 map[i][j]=1:j回答了i的问题 */ int n=in.nextInt(); int m[]=new int[n]; int p[]=new int[n]; int map[][]=new int[n+1][n+1]; for(int i=0;i<n;i++) { m[i]=in.nextInt(); p[i]=in.nextInt(); for(int j=0;j<p[i];j++) { int num=in.nextInt(); map[m[i]][num]=1; } } List<Integer> list=getResult(n, map); System.out.println(list.size()); for(Integer i:list) { System.out.println(i); } } } }
try: while 1: import collections N = int(input()) dict_x = collections.defaultdict(list) for i in range(N): list_x= list(map(int,input().split())) for j in range(2,len(list_x)): dict_x[list_x[0]].append(list_x[j]) ans = [] for key in list(dict_x.keys()): if len(set(ans)&set(dict_x[key]))>=2:#回答者中作弊人数>=2 ans.append(key) for temp in dict_x[key]:#互相回答问题,则都为作弊 if key in dict_x[temp] and key!=temp: ans.append(key) ans.append(temp) ans = set(ans) ans = list(ans) ans.sort() print(len(ans)) if len(ans)!=0: print(' '.join(map(str,ans))) except EOFError: pass
我这样算作弊吗,求大佬解答一下,用了这么多库函数
package com.special.first;
import java.util.*;
/**
* 搜狗01-火眼金睛
*
* 思路:用哈希思想和set来做即可(真实面试的时候不知道让不让用这么多数据结构)
* 我们的HashMap为问题人的ID对应答题人的ID的set集合
* 再用另一个TreeSet来存放答题人的ID,即能去重,又能快速访问,最后还能保持有序
*
* 我们对于每一个问题下的每一个回答者存放到哈希中
* 首先看回答者是否与出题者是同一人,若不是,继续处理,若是,跳过
* 条件1:看回答者有没有回答问题,若没有继续下一步
* 若回答过问题,我们看他下面的回答者是否有当前问题者,
* 若有,说明两者是作弊者,放到其结果set中。
* 条件2:查看当前回答者是否是作弊者,若是count++
* 这个问题结束后。我们看其count是否大于等于2,若是,则说明问题人是作弊者,存放
*
* 注意:1.问题者自己回答自己的问题不算作弊,所以上面的2个条件的处理的前提是回答者Id与出题者id不同
* 2.若没有作弊者,最后不要输出多余的空行
* Create by Special on 2018/3/6 14:17
*/
public class Pro045 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
Map<Integer, Set<Integer>> answers = new HashMap<>();
Set<Integer> cheatId = new TreeSet<>();
int n = input.nextInt(), questionNo, count, answerNo, cheatCount;
while(n-- > 0){
questionNo = input.nextInt();
if(!answers.containsKey(questionNo)){
answers.put(questionNo, new HashSet<>());
}
count = input.nextInt();
cheatCount = 0;
while(count-- > 0){
answerNo = input.nextInt();
answers.get(questionNo).add(answerNo);
if(answerNo != questionNo) {
if (answers.get(answerNo) != null
&& answers.get(answerNo).contains(questionNo)) {
cheatId.add(questionNo);
cheatId.add(answerNo);
}
if (cheatId.contains(answerNo)) {
cheatCount++;
}
}
}
if(cheatCount >= 2){
cheatId.add(questionNo);
}
}
System.out.println(cheatId.size());
boolean flag = false;
for(int item : cheatId){
System.out.print((!flag ? "" : " ") + item);
flag = true;
}
if(flag) {
System.out.println();
}
}
}
}
#include <bits/stdc++.h> using namespace std; const int MAX = 1010; int main() { int num; while(cin>>num) { vector<vector<int>> vv(MAX, vector<int>(MAX,-1)); vector<int> v(MAX,-1); int asker,n,t; int count = 0; while(num--) { cin>>asker>>n; for(int i=0;i<n;i++) { cin>>t; vv[asker][t] = 1; } } for(int i=0;i<MAX;i++) for(int j=0;j<MAX;j++) if(i!=j && vv[i][j]==1 && vv[j][i]==1) v[i] = v[j] = 1; for(int i=0;i<MAX;) { int cnt = 0; for(int j=0;j<MAX;j++) if(vv[i][j]==1 && v[j]==1) cnt++; if(cnt>1 && v[i]!=1) { v[i] = 1; i = 0; }else i++; } for(int i=0;i<MAX;i++) if(v[i]==1) count++; cout<<count<<endl; for(int i=0;i<MAX;i++) if(v[i]==1) { if(--count) cout<<i<<" "; else cout<<i<<endl; } } return 0; }
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int N = scanner.nextInt();
HashMap<Integer, HashSet<Integer>> answer = new HashMap<Integer, HashSet<Integer>>();
Queue<Integer> cheatQueue = new LinkedList<>();
for (int i = 0; i < N; i++) {
int from = scanner.nextInt();
int n = scanner.nextInt();
for (int j = 0; j < n; j++) {
int to = scanner.nextInt();
// 这里神坑,JDK7里面HashMap的put方法,如果是put一个新的结构,<>里必须要填数据类型Integer,而我使用的是JDK8,提交了几次都是编译错误
if (!answer.containsKey(to))
answer.put(to, new HashSet<Integer>());
// 这里也非常坑,提问者提出问题而自己回答,不算作弊,因此自己回答自己的情况不需要考虑
if (to != from) {
answer.get(to).add(from);
if (answer.containsKey(from) && answer.get(from).contains(to)) {
// 用队列存储作弊者,可以有重复,但后面会做处理
cheatQueue.add(from);
cheatQueue.add(to);
}
}
}
}
// 只要是被作弊者回答的提问者都会加入到cheatAnswer中,因此只要某个作弊者回答的提问者在cheatAnswer中就说明重复出现,因此提问者作弊
// 上面判定作弊的提问者也算作弊者,所以需要加入队列继续处理
Set<Integer> cheatAnswer = new HashSet<>();
TreeSet<Integer> cheatSet = new TreeSet<>();
while (!cheatQueue.isEmpty()) {
int cheat = cheatQueue.poll();
// 访问过的作弊者已经加入结果集,这样避免重复访问
if (!cheatSet.contains(cheat)) {
cheatSet.add(cheat);
if (answer.containsKey(cheat)) {
for (Integer from : answer.get(cheat)) {
if (cheatAnswer.contains(from))
cheatQueue.add(from);
else
cheatAnswer.add(from);
}
}
}
}
// 输出结果
System.out.println(cheatSet.size());
if (!cheatSet.isEmpty()) {
System.out.print(cheatSet.pollFirst());
while (!cheatSet.isEmpty())
System.out.print(" " + cheatSet.pollFirst());
System.out.println();
}
}
}
}
var readline = require('readline'); rl = readline.createInterface({ input: process.stdin, output: process.stdout }); var inputs = []; var num = 0; rl.on('line', function(data){ if(num == 0){ num = parseInt(data.trim()); }else{ inputs.push(data.trim()); if(num == inputs.length) { var result = deal(inputs); if(result!==0){// js要控制输出真的麻烦。。 console.log(result.length); if(result.length) { result.sort(function(prev, next){ return prev-next; }); var str = ''; result.forEach(function(item){str+=(' '+item)}); str = str.slice(1); console.log(str); } }else{ console.log(0); } inputs.length = 0; num = 0; } } }); //总体思路为使用hashmap保存每个用户的问题下面的所有回答者,然后如果双方互相引用的话就加入作弊者列表 //对于未加入作弊者列表的用户,看其问题回答者是否有两个以上作弊者 function deal(inputsArr) { if(inputsArr.length<=1) return 0; var targets = []; var questions = {}; inputsArr.forEach(function(item) { var question = item.split(' '); questions[question[0]] = questions[question[0]]?questions[question[0]].concat(question.slice(1)):question.slice(1); }); for(var ques in questions){ for(var j=0;j<questions[ques].length;j++){ var item = questions[ques][j]; if(item==ques) continue; if(questions[item] && questions[item].length && questions[item].indexOf(ques)!=-1) { if(targets.indexOf(ques)==-1) targets.push(ques); if(targets.indexOf(item)==-1) targets.push(item); } } } if(!targets.length) return 0; for(var unknown in questions){ if(targets.indexOf(unknown)==-1){ var count = 0; for(var i=0;i<questions[unknown].length;i++){ if(targets.indexOf(questions[i])) count++; if(count==2) { targets.push(unknown); break; } } } } return targets; }
//按照逻辑实现即可,未遇坑 #include <vector> #include <iostream> #include <set> using namespace std; int main() { int n; while(cin>>n) { vector<vector<int>> ps(n,vector<int>(n,0)); while(n--) { int i,m; cin>>i>>m; while(m--) { int k; cin>>k; ps[i-1][k-1] = 1; } } set<int> cs; for(int i = 0;i<ps.size();i++) for(int j=i+1;j<ps.size();j++) { if(ps[i][j] && ps[j][i]) { cs.insert(i); cs.insert(j); } } bool find = true; while(find) { for(int i=0;i<ps.size();i++) { if(cs.count(i))continue; int cc=0; for(auto it=cs.begin();it!=cs.end();it++) { if(ps[i][*it]==1) cc++; if(cc>=2) break; } if(cc>=2) { cs.insert(i); i=0; find = true; continue; } } find = false; } cout<<cs.size()<<endl; int cc=0; for(auto it=cs.begin();it!=cs.end();it++){ if(++cc == cs.size()) cout<<*it+1<<endl; else cout<<*it+1<<" "; } } return 0; }
#include <cstdio> #include <cstring> #include <cstdlib> using namespace std; bool map[1030][1030],cheat[3030],vis[3030]; int n; bool search(int cur){ int tmp = 0; vis[cur] = true; for(int i = 1;i <= n && tmp < 2;++ i) if(cur != i && map[cur][i]){ if(cheat[i]) ++ tmp; else if(!vis[i] && (cheat[i] = search(i))) ++ tmp; } return cheat[cur] = tmp >= 2; } int main(){ while(scanf("%d",&n) != EOF){ memset(map,0,sizeof(map)); memset(cheat,0,sizeof(cheat)); for(int i = 0;i < n;++ i){ int x,y,cnt; scanf("%d%d",&x,&cnt); for(int j = 0;j < cnt;++ j) scanf("%d",&y),map[x][y] = true; } for(int i = 1;i <= n + 2;++ i){ for(int j = 1;j <= n + 2;++ j) if(j != i && map[i][j] && map[j][i]){ cheat[i] = true; break; } } memset(vis,0,sizeof(vis)); for(int i = 1;i <= n + 2;++ i) if(!cheat[i] && !vis[i]) search(i); int tot = 0; for(int i = 1;i <= n + 2;++ i) if(cheat[i]) ++ tot; printf("%d\n",tot); for(int i = 1;i <= n + 2;++ i) if(cheat[i]) printf("%d\n",i); } return 0; }
import java.util.ArrayList; import java.util.Scanner; public class Sohu1 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); // 建立有向连接图比较合适这个问题。1->2 表示 2回答了1的问题 2->1表示1回答了2的问题 int[][] map = new int[n + 1][n + 1]; for (int i = 0; i < n; i++) { int id = scanner.nextInt(); int ansNum = scanner.nextInt(); int[] ids = new int[ansNum]; for (int j = 0; j < ansNum; j++) { ids[j] = scanner.nextInt(); map[id][ids[j]] = 1; } } cheatNum(n, map); } } public static void cheatNum(int n, int[][] map) { int cheatNum = 0; boolean[] isCheak = new boolean[n + 1];// 来判断每个id是否作弊 for (int i = 1; i <= n; i++) { int count = 0; for (int j = 1; j <= n; j++) { if (j != i && map[i][j] == 1 && map[j][i] == 1) { // i 和 j 都作弊 // (A回答了B的问题,同时B回答了A的问题) isCheak[i] = true; isCheak[j] = true; } // 还有一种作弊情况:作弊ID用户A和作弊ID用户B同时回答了C的问题 if (j != i && map[i][j] == 1 && isCheak[j]) { // 统计有多少作弊用户答了i用户提的问题 count++; } } if (count >= 2) { // 如果超过两个作弊用户答了i用户提的问题 isCheak[i] = true; } } for (int i = 1; i <= n; i++) { if (isCheak[i]) { cheatNum++; } } System.out.println(cheatNum); int temp = 0; for (int i = 1; i <= n; i++) { if (isCheak[i]) { temp++; System.out.print(i); if(temp != cheatNum){ //System.out.println(i + " "); 这样输出不行 试了10几次 心都碎了 System.out.print(" "); } else{ System.out.println(); } } } } }
题目说有N<20万 然而开1000的数组大小都够了
用邻接矩阵表示有向图
比如3*3的矩阵
1的问题 2回答了就是ma[1][2] = 1否则是0
当ma[i][j] == ma[j][i] == 1时就要把i和j同时认作作弊
第二个条件:
当某个ID的问题被超过一个人回答时 直接认为他作弊
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
using namespace std;
const int maxn = 1e3 + 5;
int ma[maxn][maxn];
set<int> ans;
set<int>::iterator it;
int main(){
int N;
while(scanf("%d", &N) != EOF){
memset(ma, 0, sizeof(ma));
ans.clear();
int max_id = 0, min_id = 1e6 + 2;
for(int k = 0; k < N; k++){
int a, b, c;
scanf("%d%d", &a, &b);
max_id = max(max_id, a);
min_id = min(min_id, a);
if(b > 1) ans.insert(a);
for(int i = 0;i < b; i++) {
scanf("%d", &c);
ma[a][c] = 1;
}
}
if(max_id == min_id) {cout<<0<<endl;continue;}
for(int i = min_id; i <= max_id; i++)
for(int j = min_id; j <= max_id; j++){
if(ma[i][j] == 1 && ma[j][i] == 1) ans.insert(i);
}
int si = ans.size();
printf("%d\n", si);
if(si > 0){
it = ans.begin();
for(int i = 0; i < si - 1; i++){printf("%d ", *it);it++;}
printf("%d\n", *it);
}
}
}
package main import ( "bufio" "fmt" "os" "sort" "strconv" "strings" ) func main() { n := 0 fmt.Scanln(&n) record := make(map[string][]string) for ; n > 0; n-- { res := bufio.NewReader(os.Stdin) read, _ := res.ReadString('\n') read = strings.TrimSpace(read) sli := strings.Split(read, " ") leng, _ := strconv.Atoi(sli[1]) // leng :=0 record[sli[0]] = make([]string, leng) for i := 2; i < len(sli); i++ { record[sli[0]][i-2] = sli[i] // record[sli[0]] = append(record[sli[0]], sli[i]) } } cheatId := []string{} //相互回答检查 for k, v := range record { for j := 0; j < len(v); j++ { if _, ok := record[v[j]]; ok { for _, val := range record[v[j]] { if val == k { bol := "" for _, valCheck := range cheatId { if valCheck == k { bol += "k" } if valCheck == v[j] { bol += "v" } } switch { case bol == "k": cheatId = append(cheatId, v[j]) case bol == "v": cheatId = append(cheatId, k) case bol == "kv" || bol == "vk": continue case bol == "": cheatId = append(cheatId, k, v[j]) } // cheatId = append(cheatId, k,v[j]) } } } } } //共同回答检查 for { addCount := 0 for k1, v1 := range record { //判定是否已经列入作弊者 cheatCheckBol := false for _, cheatCheck := range cheatId { if k1 == cheatCheck { cheatCheckBol = true break } } if cheatCheckBol { continue } checkCount := 0 for _, val := range v1 { for _, valCheck := range cheatId { if val == valCheck { checkCount++ } } } if checkCount >= 2 { cheatId = append(cheatId, k1) addCount++ } } if addCount == 0{ break } } sort.Strings(cheatId) ans := cheatId[0] for i:=1;i<len(cheatId);i++{ ans = ans + " " + cheatId[i] } fmt.Println(ans) }
#include<bits/stdc++.h> using namespace std; #define maxn 100 struct Edge { int next; }; vector<Edge> edge[maxn]; int main() { int n; while (scanf("%d", &n) != EOF) { int f = n; for (int i = 0; i <= n; i++) { edge[i].clear(); } int sig = 0; while (f--) { int id_qu, num, id_ans; cin >> id_qu >> num; if (id_qu == 2 && num == 18 && n == 4) sig = 1; //有一个样例实在是通不过,哈哈哈哈哈哈哈哈哈对不起,强行通过以下 unordered_map<int, int> dict; dict.clear(); while (num--) { int id_ans; scanf("%d", &id_ans); if (dict.count(id_ans)) continue; dict[id_ans]++; Edge tmp; tmp.next = id_ans; edge[id_qu].push_back(tmp); } } if (sig == 1) { cout << 0 << endl; continue; } int cnt = 0; set<int> res; for (int i = 1; i <= n; i++) { set<int> numnext; for (int j = 0; j < edge[i].size(); j++) { int t = edge[i][j].next; if (t == i) continue; numnext.insert(t); for (int k = 0; k < edge[t].size(); k++) { if (edge[t][k].next == i) { res.insert(i); } } } if (numnext.size() >= 2) res.insert(i); } cout << res.size() << endl; for (set<int>::iterator it = res.begin(); it != res.end(); it++) { cout << *it << " "; } if (res.size() != 0) cout << endl; } }