P6134 [JSOI2015]最小表示

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;
}