AFO人回归变蒟蒻
查看原帖
AFO人回归变蒟蒻
240145
Iambinary楼主2022/11/18 20:11

BFS段错误, DFS WA

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e5 + 3, M = 1e6 + 3;
int to[M], h[N], nxt[M], cnt, n, m;
bool vis[N];

void add(int u, int v) {
	to[++cnt] = v;
	nxt[cnt] = h[u];
	h[u] = cnt;
}

void bfs(int s) {
	int que[M], l = 0, r = 0;
	que[++r] = s;
	while(l < r) {
		int x = que[r];
		++l;
		printf("%d ", x);
		vis[x] = 1;
		priority_queue <int, vector <int>, greater<int> > q; 
		for(int u = h[x]; u; u = nxt[u]) {
			if(!vis[to[u]]) {
				vis[to[u]] = 1;
				q.push(to[u]);
			}
		}
		while(!q.empty()) {
			que[++r] = q.top();
		}
	}
}

void dfs(int x) {
	if(vis[x]) return;
	vis[x] = 1;
	printf("%d ", x);
	priority_queue <int, vector <int>, greater<int> > q; 
	for(int u = h[x]; u ; u = nxt[u]) {
		q.push(to[u]);
	}
	while(!q.empty()) {
		dfs(q.top());
		q.pop();
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
	}
	bfs(1);
	printf("\n");
	memset(vis, 0, sizeof vis);
	dfs(1);
	return 0;
}
2022/11/18 20:11
加载中...