选举预测

题目描述

题目传送门

思路

看到 $n \le 10^6$，显然会有一些结论。

结论1

能打败人最多的人可能胜利。

证明：假设打败人最多的人（称其为 Cms）不可能胜利，那必定有人（下文称其为石老板）可以打败他和他所有能打败的人，否则可能出现 Cms 打败的人干掉了石老板，然后 Cms 干掉了他，取得胜利。为了避免这种使 Cms 胜利的情况，要使石老板打败 Cms 及 Cms 可以打败的人，这样石老板可以打败的人就会比 Cms 多，也就是 Cms 不是打败人最多的人，出现矛盾，原命题成立。

结论2

可能胜利的人打不败的人也可能胜利。

证明：假设有一个可能胜利的人叫做 Cms，而 Cms 不一定可以打败石老板。这样 Cms 可以将出了石老板外的所有人干掉（因为 Cms 可能胜利），然后石老板再干掉 Cms，石老板就可以取得胜利。

知道了这两点，我们可以将可能胜利的人加入搜索队列，然后用枚举队首可能打不败的人，执行搜索，即可得到答案。

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10;

int Head[MAXN] , Ver[MAXN * 4] , Next[MAXN * 4];
int ToT; 

void Add(int u , int v) {
	Ver[++ToT] = v;
	Next[ToT] = Head[u];
	Head[u] = ToT;
}

int N;
queue<int> q;

vector<int> G[MAXN];
int MayBeWinner[MAXN] , Ans;

int Nxt[MAXN] , Pre[MAXN];

void Delete(int p) {
	Nxt[Pre[p]] = Nxt[p];
	Pre[Nxt[p]] = Pre[p];
}

void BFS() {
	while(q.size()) {
		int x = q.front();
		q.pop();
		int p = Pre[N + 1];
		int i = Head[x];
		while(p != 0) {
			while(p < Ver[i] && i != 0) {
				i = Next[i];
			}
			if(p != Ver[i]) {
				MayBeWinner[p] = true;
				Delete(p);
				Ans++;
				q.push(p);
			}
			p = Pre[p];
		}
	}
}

int CntCanWin[MAXN];
int MaxCanWin;
int Num[MAXN];

int main() {
//	freopen("ele.in" , "r" , stdin);
//	freopen("ele.out" , "w" , stdout);
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);	
	
	cin >> N;
	for(int i = 1; i <= N; i++) {
		cin >> CntCanWin[i];
		MaxCanWin = max(MaxCanWin , CntCanWin[i]);
		for(int j = 1; j <= CntCanWin[i]; j++) {
			cin >> Num[j];
		}
		sort(Num + 1 , Num + 1 + CntCanWin[i]);
		for(int j = 1; j <= CntCanWin[i]; j++) {
			Add(i , Num[j]);
		}
	}
	
	for(int i = 1; i <= N + 1; i++) {
		Pre[i] = i - 1;
		Nxt[i] = i + 1;
	}
	
	for(int i = 1; i <= N; i++) {
		if(CntCanWin[i] == MaxCanWin) {
			MayBeWinner[i] = true;
			q.push(i);
			Delete(i);
			Ans++;
		}
	}
	
	BFS();
	
	cout << Ans << " ";
	for(int i = 1; i <= N; i++) {
		if(MayBeWinner[i]) {
			cout << i << " ";
		}
	}
	cout << endl;
	return 0;
}