这题如果用tarjan+记忆化搜索做的话
inline void dfs(int x) {
if(size[scc[x]]>1) {
ans[x]=size[scc[x]];
return ;
} else {
ans[x]=1;
dfs(e[head[x]].to);
ans[x]+=ans[e[head[x]].to];
}
}
这样写就会MLE三个点,改成下面这样才能AC
原因就是如果不加上这个判断就有可能会把已经求出来的答案再求一遍,dfs递归太多会爆
inline void dfs(int x) {
if(size[scc[x]]>1) {
ans[x]=size[scc[x]];
return ;
} else {
ans[x]=1;
if(!ans[e[head[x]].to])
dfs(e[head[x]].to);
ans[x]+=ans[e[head[x]].to];
}
}