POI - Mafia

Author: Benjamin Qi

Table of Contents

Edit on Github

Similar to "POI - Spies." Maximum is easy. For minimum, we want to choose a subset of participants of maximum size such that no participant in the subset shoots at another. This can again be done with a greedy strategy.

int n, spy[MX], ST[MX], EN[MX], adj[MX];
bitset<MX> vis, used;


int sum;


void dfs(int _) {
    vi st = {_};
    while (sz(st)) {
        int x = st.bk; vis[x] = 1;
        if (ST[x] == EN[x]) {

Give Us Feedback on POI - Mafia!