bfs 反向建边 wa了八个点 求助
  • 板块P3916 图的遍历
  • 楼主witw
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/1/17 12:10
  • 上次更新2023/10/28 12:09:51
查看原帖
bfs 反向建边 wa了八个点 求助
570507
witw楼主2022/1/17 12:10
#include<iostream>
#include<queue>
#include<vector>
#include<cstring> 
using namespace std;
const int N=100005;
vector<int>edge[N];
queue<int>q;
int d[N];
int f[N];
int main(){
	int n,m,i,x,y,k;
	cin>>n>>m;
	memset(d,0,sizeof d);
	for(i=1;i<=n;++i)f[i]=i;
	for(i=0;i<m;++i){
		cin>>x>>y;
		edge[y].push_back(x);
		d[x]++;
	}
	for(i=1;i<=n;++i)if(d[i]==0)q.push(i);
	while(!q.empty()){
		x=q.front();
		q.pop();
		for(i=0;i<edge[x].size();++i){
			k=edge[x][i];
			f[k]=max(f[k],f[x]);
			d[k]--;
			if(d[k]==0)q.push(k);
		}
	}
	for(i=1;i<=n;++i)cout<<f[i]<<" ";
	return 0;
} 
2022/1/17 12:10
加载中...