其实这道题可以不用拓扑排序,就直接dfs
重要是一个节点的可达点为其直接相连的可达点的可达点的交集
呵呵,断个句
重要是一个节点的可达点为/其直接相连的可达点/的可达点的交集
还是上码吧
#include <bits/stdc++.h>
using namespace std;
vector<int> a[30010];
int v[30010], n, m;
bitset<30010> f[30010];
void dfs(int k){
v[k] = 1;
f[k][k] = 1;
for (int i = 0; i < a[k].size(); i ++ ){
if (!v[a[k][i]]) dfs(a[k][i]);
f[k] |= f[a[k][i]];
}
return;
}
int main(){
cin >> n >> m;
for (int i = 1, x, y; i <= m; i ++ ){
cin >> x >> y;
a[x].push_back(y);
}
for (int i = 1; i <= n; i ++ ){
if (v[i]) continue;
dfs(i);
}
for (int i = 1; i <= n; i ++ ) cout << f[i].count() << endl;
}
好像只比题解慢几ms
是不是省时省力?