阅读前提示：这是笔者（暂且这么称呼罢）第一篇 MarkDown 文章，排版什么的都比较毒瘤（尽管经过了后续优化），谨慎食用
这道题花了我四天的时间才想出来，主要是卡在 非暴力解法（时间复杂度） 和 空间复杂度优化 的问题上
搜索
首先看到题面想到的肯定是暴力搜索，这种做法能拿到60分（我只拿了20），这里是@Star 王亚飞提供的暴力搜索代码。
由于有 个点的图最多有 条边，所以这里的图很明显是稀疏图，适宜用邻接表存
#include <bits/stdc++.h>
using namespace std;
const int N = 30010;
int n, m;
vector<int> g[N];
int ans[N], visit[N];//注意防止重复访问
void dfs(int x){
visit[x] = 1;
for(int i = 0; i < g[x].size(); ++i){
int to = g[x][i];
if(visit[to] == 0){
dfs(to);
}
}
}
int main() {
scanf("%d%d", &n, &m);
while(m--){
int from, to;
scanf("%d%d", &from, &to);
g[from].push_back(to);
}
for(int i = 1; i <= n; ++i){
memset(visit, 0, sizeof(visit));
dfs(i);
for(int j = 1; j <= n; ++j){
if(visit[j] == 1)
++ans[i];
}
}
for(int i = 1; i <= n; ++i){
printf("%d\n", ans[i]);
}
return 0;
}
我当时的第一想法是按照拓扑序遍历，在遍历到一个点时再往回搜索，将搜索到的所有点的可达点数加一。 这个想法不是很成熟，但是它把我引导到了一个更好的思路上。
另一种思路
既然按照拓扑序遍历的话必须往回搜才行，那为什么不倒着遍历呢？
于是就有了这个思路：
将整个图按照拓扑逆序遍历，每一个点的可达数就是它的前驱可达数之和，初始化每个点都能走到自己。
但是我们按照这个思路敲出来过不了样例，画图把样例推一遍可以知道原因是点重复计算。
所以最终的思路是：
每个点的可达点是它前驱可达点的并集。
思路有了，接下来就是实现的问题。
我们可以很自然地想到用一个bool数组存储可达点，并在按照拓扑序遍历的时候将它们进行并集运算。
#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
const int MAXN = 10010;//否则数组太大会RE
int n, m;
vector<int> g[MAXN];
bool s[MAXN][MAXN];
queue<int> q;
int deg[MAXN];
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
g[y].push_back(x);
deg[x]++;
}
for (int i = 1; i <= n; i++) {
s[i][i] = true;
if (deg[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int t = q.front();
q.pop();
int k = g[t].size();
for (int i = 0; i < k; i++) {
int x = g[t][i];
for (int i = 1; i <= n; i++) {
if (s[t][i]) {
s[x][i] = 1;
}
}
deg[x]--;
if (deg[x] == 0) {
q.push(x);
}
}
}
for (int i = 1; i <= n; i++) {
int ans = 0;
for (int j = 1; j <= n; j++) {
if (s[i][j]) {
ans++;
}
}
cout << ans << endl;
}
return 0;
}
这个算法的好处是不但解决了点的重复计算的问题，还解决了边的去重的问题。
即当两点间有多条边的时候，无论执行多少遍并集操作都不会影响最终的计数。
但是缺点依旧是时间复杂度和空间复杂度过高。
虽然相较于搜索有所优化，但在30000的巨大数据面前还是撑不住。
这个代码最终能拿到80分。
优化
分析上述算法的核心代码可以发现复杂度主要还是耗在并集操作上。
优化的方法要用到之前的知识——或运算
我们如果能将一个一维bool数组转化为一个二进制数字存储，即将原数组对应下标位置的值存储在这个二进制数的对应位上，那么在执行并集操作时就能转化为对两个二进制数字执行按位或运算，效率会大幅提高，同时一个bool类型的数占空间1 byte = 8 bit，但一个二进制位仅占位1 bit，空间复杂度可以优化到八分之一。
根据进阶指南上的定义这就是二进制状态压缩，具体实现方法可以用普通数组配合二进制运算实现，但是万能的C++ STL给我们提供了一个叫bitset的好东西。
话不多说直接看代码。
#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
const int MAXN = 30010;
int n, m;
vector<int> g[MAXN];
bitset<MAXN> s[MAXN];
queue<int> q;
int deg[MAXN];
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
g[y].push_back(x);
deg[x]++;
}
for (int i = 1; i <= n; i++) {
s[i][i] = true;
if (deg[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int t = q.front();
q.pop();
int k = g[t].size();
for (int i = 0; i < k; i++) {
int x = g[t][i];
s[x] |= s[t];
deg[x]--;
if (deg[x] == 0) {
q.push(x);
}
}
}
for (int i = 1; i <= n; i++) {
cout << s[i].count() << endl;
}
return 0;
}
这个代码就足以AC这道题。
总结与收获
虽然四天做一道题耗时有点久，但我也不是完全没有收获。
这道题首先启发我的是在遇到难题的时候可以先试着打暴力，虽然有人能直接A在打暴力的时候说不定就会有所启发想到更好的算法。
第二个是样例过不去的时候可以按照自己的代码手推一遍，能发现不少代码中的问题其实这个是从别人那学的。
最大的收获其实还是做题的成就感
共 3 条回复
怎么有人挖坟这种毒瘤文章还是别看了（悲
tql
某个提供TLE代码的人站起来了
树形dp:从叶子到根自下往上状态转移