题意：给你一张DAG，让你选取最多的点，使得这些点之间互相不可达。
思路：此问题和最小路径可重复点覆盖等价，先在原图上跑一边传递闭包，然后把每个点拆成两个点i, i + n, 原图中的边(a, b)变成(a, b + n)，跑一变网络流, 答案就是n - maxflow;
代码：
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 305;
const int maxm = 100010;
bitset<maxn> b[maxn];
queue<int> q;
int head[maxn], ver[maxm], Next[maxm], edge[maxm], d[maxn];
vector<int> G[maxn];
int n, m, s, t, tot, maxflow;
bool v[maxn];
void dfs(int x) {
if(v[x]) return;
b[x][x] = 1;
for (auto y : G[x]) {
dfs(y);
b[x] |= b[y];
}
v[x] = 1;
return;
}
void add(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}
bool bfs() {
memset(d, 0, sizeof(d));
while(q.size()) q.pop();
q.push(s);d[s] = 1;
while(q.size()) {
int x= q.front();
q.pop();
for (int i = head[x]; i; i = Next[i]) {
if(edge[i] && !d[ver[i]]) {
q.push(ver[i]);
d[ver[i]] = d[x] + 1;
if(ver[i] == t) return 1;
}
}
}
return 0;
} int dinic(int x, int flow) {
if(x == t) return flow;
int rest = flow, k;
for (int i = head[x]; i && rest; i = Next[i]) {
if(edge[i] && d[ver[i]] == d[x] + 1) {
k = dinic(ver[i], min(rest, edge[i]));
if(!k) d[ver[i]] = 0;
edge[i] -= k;
edge[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}
int main() {
int T, x, y;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
tot = 1;
s = n * 2 + 1, t = n * 2 + 2;
for (int i = 1; i <= n; i++)
b[i].reset();
memset(head, 0, sizeof(head));
for (int i = 1; i <= n; i++) {
G[i].clear();
v[i] = 0;
}
maxflow = 0;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
}
for (int i = 1; i <= n; i++) {
if(!v[i]) {
dfs(i);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(i == j) continue;
if(b[i][j] == 1) {
add(i, j + n, 1);
}
}
}
for (int i = 1; i <= n; i++) {
add(s, i, 1);
add(i + n, t, 1);
}
int flow = 0;
while(bfs())
while(flow = dinic(s, INF)) maxflow += flow;
printf("%d\n", n - maxflow);
}
return 0;
}