C++(g++ 7.5.0) 解法, 执行用时: 288ms, 内存消耗: 198764K, 提交时间: 2022-08-28 21:56:03

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 4e4+15;
int in[N];
vector<int>E[N];
bitset<N>bt[N];
int n,m;
void topu(){
	int ans=0;
	queue<int>q;
	bt[1][1]=1;
	q.push(1);
	while(!q.empty()){
		int u=q.front();q.pop();
		if(bt[u].count()&1){
			ans++;bt[u][u]=1;
		}
		for(auto v:E[u]){
			in[v]--;
			bt[v]|=bt[u];
			if(!in[v])
				q.push(v);
		}
	}
	cout<<ans<<'\n';
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v;cin>>u>>v;
		E[u].pb(v);in[v]++;
	}
	topu();
}

C++14(g++5.4) 解法, 执行用时: 491ms, 内存消耗: 204500K, 提交时间: 2020-06-18 15:38:05

#include<bits/stdc++.h>
using namespace std;
const int N=4e4+1000;
int n,m,u,v;
vector<int> G[N];
int in[N];
bitset<N> f[N];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		G[u].push_back(v);
		in[v]++;
	}
	queue<int> q;
	for(int i=1;i<=n;i++) if(in[i]==0)  q.push(i);
	f[1][1]=1;
	int ans=0;
	while(q.size())
	{
		auto t=q.front();q.pop();
		if(f[t].count()&1) f[t][t]=1,ans++;
		for(auto x: G[t]){
			f[x]|=f[t];
			if(--in[x]==0) q.push(x);
		}
	}
	cout<<ans<<endl;
 } 

C++ 解法, 执行用时: 308ms, 内存消耗: 198784K, 提交时间: 2021-11-01 16:49:53

#include<bits/stdc++.h>
using namespace std;
const int N=4e4+5;
bitset<N>bt[N];
int n,m,ans,du[N];
vector<int>mp[N];
queue<int>p;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		mp[x].push_back(y);
        du[y]++;
	}
	p.push(1);
	bt[1][1]=1;
	while(p.size()){
		int x=p.front();
		p.pop();
		if(bt[x].count()&1){
			ans++;
			bt[x][x]=1;
		}
		for(auto y:mp[x]){
			bt[y]|=bt[x];
			if(--du[y]==0)p.push(y);
		}
	}
	printf("%d",ans);
}