关于拓扑更新
查看原帖
关于拓扑更新
249422
TinyMirror1楼主2020/10/27 10:40

我一开始时在点入度为0是就直接更新深度和倍增数组,然后5#Wa了

后来改为一个点出队时更新就AC了

请问这两种更新有什么区别吗,为什么第一个错了


第一种更新:

void topo() {
	q.push(0);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = first[now]; i; i = ed[i].next) {
			int v = ed[i].to;
			if (f[v][0] == -1) {
				f[v][0] = now;
			} else {
				f[v][0] = lca(f[v][0], now);
			}
			in[v]--;
			if (in[v] == 0) {
				q.push(v);
				n_insert(f[v][0], v);
				d[v] = d[f[v][0]] + 1;
				for (int j = 1; j <= log2[d[v]]; j++) {
					f[v][j] = f[f[v][j - 1]][j - 1];
				}
			}
		}
	}
}

第二种更新:

void topo() {
	q.push(0);
	while (!q.empty()) {
		int now = q.front(); q.pop();
		n_insert(f[now][0], now);
		d[now] = d[f[now][0]] + 1;
		for (int j = 1; j <= log2[d[now]]; j++) {
			f[now][j] = f[f[now][j - 1]][j - 1];
		}
		for (int i = first[now]; i; i = ed[i].next) {
			int v = ed[i].to;
			if (f[v][0] == -1) {
				f[v][0] = now;
			} else {
				f[v][0] = lca(f[v][0], now);
			}
			in[v]--;
			if (in[v] == 0) {
				q.push(v);
			}
		}
	}
}
2020/10/27 10:40
加载中...