一个并查集引发的血案

事情缘由

事情是这样的，今天第二次做"关押罪犯”一题，奇迹般的MLE了4个点。

一开始想要优化并查集点写法，不想费事初始化，于是有了以下代码

int f[N];
int find(int x)
{
    if(f[x])
        return f[x] = find(f[x]);
    return x;
}
void merge(int x, int y)
{
    f[find(x)] = find(y);
}

看着没有什么问题。

事情的发展

后来发现把代码改成这样就没有问题了。

int find(int x)
{
    if(f[x] != x)
        return f[x] = find(f[x]);
    return x;
}
//加初始化

但是这样又违背了初衷，感觉很奇怪。 ## 事情的解决 在十几篇博客中的某篇博客的注释中，发现了我的问题所在：如果merge(i,i)，也就是在同一棵子树上的两个节点，再find(i)，就会认为某个节点是子节点，它的父节点也是自己，造成死循环/无限递归，至于是M还是T，取决于时间空间限制。做如下改动就行了

void merge(int x, int y)
{
    int rx = find(x), ry = find(y);
	rx != ry ? f[rx] = find(ry): 0 ;
}