Upd：卡过去了，但是 986 ms，有没有人知道原因 qwq
by NASFsky @ 2023-11-10 13:53:31
@[NASFsky](/user/375403) 要是有超过 $8000$ 个强连通分量您的代码是不是直接 RE 了 qwq
而且感觉 dfs 可以卡到 $\mathcal O(nV)$，具体大概是这个样子：
```cpp
/**
* author: sunkuangzheng
* created: 10.11.2023 13:56:34
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
debug_helper deg;
#endif
using namespace std;
int t,n = 480000,m = 483997;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
freopen("testcode.in","w",stdout);
cout << n << " " << m << "\n";
for(int i = 2;i <= 4000;i ++) cout << "1 " << i << "\n",cout << i << " 4001\n";
for(int i = 4001;i < n;i ++) cout << i << " " << i + 1 << "\n";
for(int i = 1;i <= n;i ++) cout << min(i,4000) << " ";
cout << "\n1 " << n << "\n";
for(int i = 1;i <= n;i ++) cout << i << " ";
}
```
by _sunkuangzheng_ @ 2023-11-10 14:09:34
@[NASFsky](/user/375403) `bool con[8000][8000]`
显然不对。
但是事实上需要判断的对数只有 $\mathcal{O}(m)$ 个，使用 `std::map<std::pair<int, int>, bool>` 即可，带个 $\log $
by lzyqwq @ 2023-11-10 15:19:09
@[蒟蒻·廖子阳](/user/539211) 可是我的代码只能勉强卡过去，再带个 $\log$ 那不更加炸裂了/xia
by NASFsky @ 2023-11-10 15:29:19
本来我也想直接开 `map` 统计的，但是考虑到强连通分量估计不会很多就直接开数组了
by NASFsky @ 2023-11-10 15:29:56
@[NASFsky](/user/375403) 不是很懂为啥只有 8000 个 scc，而且有时候空间开太大时间也会炸的
而且不懂这题貌似不要去重边的吧
by lzyqwq @ 2023-11-10 15:31:30
@[蒟蒻·廖子阳](/user/539211) $8000$ 个是我感性理解的/cf 估计它不会很多，没有依据。去重边我是防止 `dfs` 跑重复太多次
by NASFsky @ 2023-11-10 15:32:45
@[NASFsky](/user/375403) 那可以让每个点只被跑一次吧，记录一下每个点有没有被访问过
by lzyqwq @ 2023-11-10 15:34:08
@[蒟蒻·廖子阳](/user/539211) 被访问了还是能被更新的吧，那不还得继续往后传递信息
by NASFsky @ 2023-11-10 15:36:10
@[NASFsky](/user/375403) 就类似记忆化搜索的拓扑排序那样
by lzyqwq @ 2023-11-10 15:37:06