求助这个思路哪里错了
查看原帖
求助这个思路哪里错了
1008001
lg15166366290楼主2024/9/15 11:47

rt,思路是在拓扑排序时把当前所有入度为零的点找出来,统计其他点被他们指向的次数,如果只有一个点进队且这个点被指向的次数恰好是当前所有入度为零的点的个数,那么这个点的排名是可确定的

说的不清楚,看代码

int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		addedge(u,v);
		in[v]++;
	}
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(!in[i])q.push(i);
	}
	if(q.size()==1)ab[q.front()]=1;
	while(!q.empty()){
		memset(pto,0,sizeof(pto));
		int cnt=q.size();
		queue<int>tmp;
		
		while(!q.empty()){
			int i=q.front();
			q.pop();
			for(int j=head[i];j;j=e[j].next){
				int v=e[j].v;
				
				pto[v]++;
				
				in[v]--;
				if(!in[v])tmp.push(v);
			}
		}
		
		if(tmp.size()==1&&pto[tmp.front()]==cnt)ab[tmp.front()]=1;
		while(!tmp.empty()){
			q.push(tmp.front());
			tmp.pop();
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(ab[i]){
			ans++;
		}
	}
	cout<<ans<<"\n";
	return 0;
}
2024/9/15 11:47
加载中...