反向广搜60pts求调
  • 板块P3916 图的遍历
  • 楼主garychu
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/19 12:51
  • 上次更新2024/11/19 17:03:27
查看原帖
反向广搜60pts求调
997660
garychu楼主2024/11/19 12:51
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> mp[N];
queue<int> q;
int vis[N],tot;
void init(){
	queue<int> emp;
	swap(q,emp);
}
void bfs(int st){
	init();
	q.push(st);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=st;
		tot++;
		int len=mp[u].size();
		for(int i=0;i<len;i++){
			int v=mp[u][i];
			if(vis[v])	continue;
			q.push(v);
		}
	}
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		mp[v].push_back(u);
	}
	for(int i=n;i>=1;i--){
		if(vis[i])	continue;
		bfs(i);
		if(tot==n)	break;
	}
	for(int i=1;i<=n;i++)
		cout<<vis[i]<<" ";
	return 0;
}
2024/11/19 12:51
加载中...