自动搬运

查看原文

来自洛谷，原作者为

	zzx0102 原 sto_5k_orz || AFO on 2023.10.21

搬运于2025-08-24 22:29:13，当前版本为作者最后更新于2023-05-03 21:45:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

显然，如果没有人和巫师 $1$ 决斗，则只有 $1$ 可能有。

否则，考虑 dfs。

反向建边，先处理出所有击败的关系。

然后从 $1$ 开始 dfs，如果 $u$ 可以干掉 $1$，那么显然 $u$ 就有机会拿到。那么同理，所有可以干掉 $u$ 的巫师 $v$ 也可以拿到，dfs 下去。

注意特判。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 100010; vector<int> e[N]; int n, m, a, ans, b; bool can[N];
void dfs(int u) {for(int v: e[u]) if(!can[v]) can[v] = 1, dfs(v);}
int main() {
	cin >> n >> m; for(int i = 0; i < m; i++) {cin >> a >> b; e[b].pb(a);}
	if(e[1].empty()) can[1] = 1; // 特判
	dfs(1); for(int i = 1; i <= n; i++) cout << can[i];
	return 0;
}