输入样例：
10 10
8 9
2 8
4 6
4 9
7 8
2 8
1 8
3 4
3 4
2 7
输出样例#6：
5
话说这题虽然不是很OI但是确实挺锻炼思维的
一开始以为是用并查集之类的东西维护
然后想了好久还是煤油想出来
正解是一个递推？模拟？贪心？
维护n个集合
我们设(f[i][j])表示如果要让(i)活到最后(j)应不应该死
可以考虑时间倒流
一开始(f[i][i]=true)
然后倒着循环操作
如果两只鸡有一只已经死了，那么另一只在这回合必须死
如果两只鸡有两只都活着，就随便死一个
如果两个都死了，那么这个鸡(i)就只能死了
最后查询的时候如果两个集合有交集
那这两只鸡就不能同时活到最后
因为如果有交集说明有一个鸡同时要给两只鸡当挡箭牌
但是一只鸡只能死一次
统计一下答案就好辣
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
# define LL long long
const int M = 405 ;
const int N = 100005 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
LL Ans ;
int n , m ;
int a[N] , b[N] ;
bool f[M][M] , die[M] ;
int main() {
n = read() , m = read() ;
for(int i = 1 ; i <= m ; i ++)
a[i] = read() , b[i] = read() ;
for(int i = 1 ; i <= n ; i ++) {
f[i][i] = true ;
for(int j = m ; j >= 1 ; j --) {
bool x = f[i][a[j]] , y = f[i][b[j]] ;
// x : 目前a[j]是否死了
// y : 目前b[j]是否死了
if(x & y) { die[i] = true ; break ; }
else if(x) f[i][b[j]] = true ;
else if(y) f[i][a[j]] = true ;
}
}
for(int i = 1 , tot ; i < n ; i ++) {
if(die[i]) continue ;
for(int j = i + 1 ; j <= n ; j ++) {
if(die[j]) continue ;
tot = 1 ;
for(int k = 1 ; k <= n ; k ++)
if(f[i][k] & f[j][k])
tot = 0 ;
Ans += tot ;
}
}
cout << Ans << endl ;
return 0 ;
}