AtCoder

分析

考虑求出如果钦定 $i$ 活到最后，那么有哪些火鸡需要送死。

倒着考虑每个人。如果 $x_i,y_i$ 后面都需要送死，那么 $i$ 必死；否则随便找一个后面不要送死的送死即可。

可以发现 $i,j$ 可能同时活到最后当且仅当不存在一只火鸡既需要为 $i$ 送死、又需要为 $j$ 送死，可以用 bitset 加速判断。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400+10,M=100000+10;

int n,m,x[M],y[M];
bitset<N> oho[N];
bool gg[N];

int main() {
    n=read(),m=read();
    for (int i=1;i<=m;++i) x[i]=read(),y[i]=read();
    for (int i=1;i<=n;++i) {
        oho[i][i]=1;
        for (int j=m;j;--j) {
            int u=x[j],v=y[j];
            if (oho[i][u]&&oho[i][v]) { gg[i]=1; break; }
            else if (oho[i][u]) oho[i][v]=1;
            else if (oho[i][v]) oho[i][u]=1;
        }
    }
    int ans=0;
    for (int i=1;i<=n;++i) {
        if (gg[i]) continue;
        for (int j=i+1;j<=n;++j) {
            if (gg[j]) continue;
            if (!(oho[i]&oho[j]).any()) ++ans;
        }
    }
    printf("%d\n",ans);
    return 0;
}