我一开始时在点入度为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);
}
}
}
}