WA 0 求助
查看原帖
WA 0 求助
556362
Unnamed114514楼主2022/5/14 09:26
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4+5;
int n,m,cnt[maxn],sum;
queue<int> q;
vector<int> G[maxn];
bitset<maxn> dp[maxn];
inline int read(){
    int res=0,f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
    	f|=(ch=='-');
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        res=(res<<1)+(res<<3)+(ch^'0');
        ch=getchar();
    }
    return f?-res:res;
}
inline void TopSort(){
	for(int i=1;i<=n;++i)
		if(!cnt[i])
			q.push(i);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0,len=G[u].size();i<len;++i){
			int v=G[u][i];
			sum+=(dp[u]&dp[v]).count();
			dp[v]|=dp[u];
			dp[v].set(u,1);
			--cnt[v];
			if(!cnt[v])
				q.push(v);
		}
	}
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;++i){
		int u=read(),v=read();
		G[u].push_back(v); 
		++cnt[v];
	}
	TopSort();
	printf("%d\n",sum);
	return 0;
}
2022/5/14 09:26
加载中...