在代码中中的merge函数里,有如下两个代码段:
for (int i = head[x]; i; i = nxt[i])
{
int j = e[i];
//color[j] = y;
res -= (color[j - 1] == y) + (color[j + 1] == y);
}
for (int i = head[x]; i; i = nxt[i])
{
int j = e[i];
color[j] = y;
if (nxt[i] == 0)
{
nxt[i] = head[y], head[y] = head[x];
break;
}
}
我原本认为 color[j] = y 在哪个函数里放着都是一样的,但是反过来放就是错误的:
for (int i = head[x]; i; i = nxt[i])
{
int j = e[i];
color[j] = y;
res -= (color[j - 1] == y) + (color[j + 1] == y);
}
for (int i = head[x]; i; i = nxt[i])
{
int j = e[i];
//color[j] = y;
if (nxt[i] == 0)
{
nxt[i] = head[y], head[y] = head[x];
break;
}
}