C++14(g++5.4) 解法, 执行用时: 672ms, 内存消耗: 860K, 提交时间: 2019-10-05 23:13:33

#include <bits/stdc++.h>

#define maxn 305
using namespace std;

int deg[maxn];
vector <int>g[maxn];
int color[maxn];
int vis[maxn];
bitset<maxn>p[maxn];

void dfs(int x){
	if(vis[x])return;
	vis[x]=1;
	
	p[x].reset();
	for(int i=0;i<g[x].size();i++){
		int v=g[x][i];
		dfs(v);
		if(!color[x]&&!color[v]){
			p[x]|=p[v];
			p[x][v]=1;	
		}		
	}
}

int main(){
	int n,m,q;
	while(scanf("%d%d%d",&n,&m,&q)!=EOF){
		for(int i=1;i<=n;i++){
			g[i].clear();
			deg[i]=color[i]=0;
		}
			
		int u,v;
		for(int i=0;i<m;i++){
			scanf("%d%d",&u,&v);
			g[u].push_back(v);
			deg[v]++;
		}
		
		while(q--){
			int x;
			scanf("%d",&x);
			color[x]^=1;
			memset(vis,0,sizeof vis);
			
			for(int i=1;i<=n;i++)
				if(deg[i]==0)
					dfs(i);
				
			int ans=0;
			for(int i=1;i<=n;i++)
				ans+=p[i].count();
			printf("%d\n",ans);
		}
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 574ms, 内存消耗: 708K, 提交时间: 2022-07-28 13:51:57

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=305;
int n,m,q,d[N];
vector <int>g[N];
bool color[N],f[N];
bitset<N>p[N];
void dfs(int x){
	if(f[x])return;
	f[x]=1;
	p[x].reset();
	for(int i=0;i<g[x].size();i++){
		int v=g[x][i];
		dfs(v);
		if(!color[x]&&!color[v]){
			p[x]|=p[v];
			p[x][v]=1;	
		}		
	}
}

int main(){
	while(cin>>n>>m>>q){
        memset(d,0,sizeof d);
        memset(color,0,sizeof color);
		for(int i=1;i<=n;i++){
			g[i].clear();
		}
		int u,v,x;
		for(int i=0;i<m;i++){
			cin>>u>>v;
			g[u].push_back(v);
			d[v]++;
		}
		while(q--){
			cin>>x;
			color[x]^=1;
			memset(f,0,sizeof f);
			for(int i=1;i<=n;i++)
				if(!d[i])
					dfs(i);
			ll ans=0;
			for(int i=1;i<=n;i++)
				ans+=p[i].count();
			cout<<ans<<endl;
		}
	}
}