很自然的想到先tarjan把强联通分量缩点，因为对于一个强联通分量，要么不选，要么全选，所以可看成一个点。
然后转化成了求DAG上的一条最长路（每一个点都有权值）。刚开始我想用dijkstra写：先把所入度为0的点都放进优先队列里，然后跑dijkstra，把所有的小于号改成大于号。
结果就WA了。
想了好半天，发现不能用dijkstra求。这和负权一样：u已经被更新了，但可能还有一条节点数很多的路径到达点u，而这个答案比当前的优，却因为u已经进过队列而更新不了。
所以只能dp。这个dp那是相当水，假设有一条边(u->v), 则dp[v] = max(dp[v], dp[u] + val[v])。然后我们从所有入度为0的点开始dp就妥了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 1e4 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int n, m;
vector<int> v[maxn]; stack<int> st;
bool in[maxn];
int dfn[maxn], low[maxn], cnt = ;
int col[maxn], val[maxn], ccol = ;
void tarjan(int now)
{
dfn[now] = low[now] = ++cnt;
st.push(now); in[now] = ;
for(int i = ; i < (int)v[now].size(); ++i)
{
if(!dfn[v[now][i]])
{
tarjan(v[now][i]);
low[now] = min(low[now], low[v[now][i]]);
}
else if(in[v[now][i]]) low[now] = min(low[now], dfn[v[now][i]]);
}
if(dfn[now] == low[now])
{
int x; ccol++;
do
{
x = st.top(); st.pop();
in[x] = ;
col[x] = ccol;
val[ccol]++; }while(x != now);
}
} vector<int> v2[maxn];
int du[maxn];
void newGraph(int now)
{
int u = col[now];
for(int i = ; i < (int)v[now].size(); ++i)
{
int e = col[v[now][i]];
if(u == e) continue;
v2[u].push_back(e);
du[e]++;
}
} int dis[maxn];
void dp(int now)
{
for(int i = ; i < (int)v2[now].size(); ++i)
{
if(dis[v2[now][i]] < dis[now] + val[v2[now][i]]) //算一个剪枝吧
{
dis[v2[now][i]] = dis[now] + val[v2[now][i]];
dp(v2[now][i]);
}
}
} void init()
{
for(int i = ; i < maxn; ++i) {v[i].clear(); v2[i].clear();}
while(!st.empty()) st.pop();
Mem(dfn, ); Mem(low, ); Mem(col, ); Mem(val, );
cnt = ccol = ;
Mem(du, ); Mem(dis, );
} int main()
{
int T = read();
while(T--)
{
init();
n = read(); m = read();
for(int i = ; i <= m; ++i)
{
int x = read(), y = read();
v[x].push_back(y);
}
for(int i = ; i <= n; ++i) if(!dfn[i]) tarjan(i);
for(int i = ; i <= n; ++i) newGraph(i);
for(int i = ; i <= ccol; ++i) if(!du[i]) dis[i] = val[i], dp(i);
int ans = ;
for(int i = ; i <= ccol; ++i) ans = max(ans, dis[i]);
write(ans); enter;
}
return ;
}