警示后人(bfs10pts)
查看原帖
警示后人(bfs10pts)
490435
PaCoCo楼主2023/7/24 22:52

如果你用bfs遍历图,9个点WA,请记住push后面紧跟vis的标记!!
错误示范(部分)

int k,n,m;
int cow[105];
vector<int> p[1005];
int kkksc03[1005];
bool vis[1005];

void bfs(int n){
	memset(vis, 0, sizeof(vis));
	queue<int> q;
	q.push(n);
	while(!q.empty()){
		int x = q.front();
		q.pop();
		kkksc03[x]++;
		vis[x] = 1;
		for(unsigned int i = 0; i<p[x].size(); i++){
			if(vis[p[x][i]]) continue;
			q.push(p[x][i]);
		}
	}
}

bfs中修改为:

void bfs(int n){
	memset(vis, 0, sizeof(vis));
	queue<int> q;
	q.push(n);
	vis[n] = 1; // 不同处1
	while(!q.empty()){
		int x = q.front();
		q.pop();
		kkksc03[x]++;
		// vis[x] = 1; 不同处2
		for(unsigned int i = 0; i<p[x].size(); i++){
			if(vis[p[x][i]]) continue;
			q.push(p[x][i]);
			vis[p[x][i]] = 1; //不同处3
		}
	}
}

我蒻,查了好久才在他人帮助下找出来这个问题

2023/7/24 22:52
加载中...