NC20218. [JSOI2015]最小表示
描述
输入描述
输入一行包含两个正整数N和M。接下来M行，每行包含两个1到N之间的正整数xi和yi，表示图中存在一条从xi到yi的有向边。输入数据保证，任意两点间只会有至多一条边存在。 N ≤ 30,000,M ≤ 100,000
输出描述
输出一行包含一个整数，表示JYY最多可以删掉的边数。
示例1
输入:
5 6 1 2 2 3 3 5 4 5 1 5 1 3
输出:
2
C++ 解法, 执行用时: 284ms, 内存消耗: 220568K, 提交时间: 2021-06-15 21:11:28
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=3e4+5,M=1e5+5;
struct Edge{int to,nxt;}e[M];
int n,m,fst[N],tote,deg[N],ans;
queue<int>q;
bitset<N>b[N],b2[N];
void adde(int u,int v){e[++tote]=(Edge){v,fst[u]};fst[u]=tote;}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),adde(u,v),deg[v]++;
for(int i=1;i<=n;i++){
b[i][i]=true;
if(!deg[i])q.push(i);
}
while(!q.empty()){
int u=q.front();q.pop();
for(int i=fst[u],v;i;i=e[i].nxt){
deg[v=e[i].to]--;b2[v]|=(b[v]&b[u]);b[v]|=b[u];
if(!deg[v])q.push(v);
}
}
for(int u=1;u<=n;u++)for(int i=fst[u];i;i=e[i].nxt)if(b2[e[i].to][u])ans++;
printf("%d\n",ans);
return 0;
}