P7370

zzx0102 · 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;
}