P6134 [JSOI2015]最小表示
思:
有向无环图，想到拓扑排序。
逆序枚举，因为排序后下标小的点用到它前面的点的联通性。
对其连接的点按照拓扑序由小到大进行排序(靠前的点可以连接的点多，那么可以删的边数也变多。
其余套路与可达性统计类似，注意代码细节。
#include <bits/stdc++.h>
#define cin std::cin
#define cout std::cout
#define endl std::endl
namespace lcj{
const int N=3e4+10,M=1e5+10;
int n,m,head[N],ne[M],e[M],idx,topo[N],deg[N],cnt,ans;//空间不要忘记开大点，有1e5次输入。
std::bitset<N> f[N];
std::queue<int> q;
std::unordered_map<int,int> mp;//哈希映射，点对应的拓扑序(dist的下标)。
void add(int x,int y){
e[++idx]=y;
ne[idx]=head[x];
head[x]=idx;
}
bool cmp(int a,int b){
return mp[a]<mp[b];
}
void main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
deg[y]++;
}
for(int i=1;i<=n;i++){
if(!deg[i]) q.push(i);
}
while(!q.empty()){
int h=q.front();
q.pop();topo[++cnt]=h;mp[h]=cnt;
for(int i=head[h];i;i=ne[i]){
int v=e[i];
deg[v]--;
if(!deg[v]) q.push(v);
}
}
for(int i=cnt;i;i--){//注意逆序
int v=topo[i];
f[v].reset();f[v][v]=1;
int a[N],len=0;
for(int j=head[v];j;j=ne[j]){
a[len++]=e[j];//可以联通的点存入数组
}
std::sort(a,a+len,cmp);//按照拓扑序排序，拓扑序小(下标)的放前面
for(int j=0;j<len;j++){
if(f[v][a[j]]) ans++;//如果可以通过别的点联通，可以删去。
else f[v] |= f[a[j]];//更新联通性
}
}
printf("%d",ans);
}
}
signed main(){
lcj::main();
return 0;
}