提问启发式合并
查看原帖
提问启发式合并
666796
Rainsleep楼主2022/12/17 10:50

在代码中中的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;
        }
    }
2022/12/17 10:50
加载中...