C++14(g++5.4) 解法, 执行用时: 306ms, 内存消耗: 113124K, 提交时间: 2020-03-21 22:27:45

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4+10;
vector<int> v[maxn];
bitset <30005> f[maxn];
void dfs(int x)
{
	if(f[x].any())	return;
	f[x][x]=1;
	for(int i=0;i<v[x].size();i++){
		dfs(v[x][i]);
		f[x]|=f[v[x][i]];
	}
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int t1,t2;scanf("%d%d",&t1,&t2);
		v[t1].push_back(t2);
	}
	for(int i=1;i<=n;i++){
		dfs(i);cout<<f[i].count()<<endl;
	}
}

C++ 解法, 执行用时: 226ms, 内存消耗: 113784K, 提交时间: 2022-07-15 14:26:54

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3e4+100;
int n,m;
bitset<N>f[N];
vector<int>edge[N];
void dfs(int x){
    if(f[x].any()) return ;
	f[x][x]=1;
	for(int i:edge[x]){
		dfs(i);
		f[x]|=f[i];
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		edge[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		dfs(i);
		cout<<f[i].count()<<endl;
	}
}