前言

an是看了某大佬的文章忽然就懂了的。
一直很想写一个解析，可是苦于没时间。
现在终于出炉了。

正文

（有点幼稚勿喷，自编）

假设我们知道有pre[i]确定了i的上级（朋友），那么问题来了。
怎么确定两个人是同意帮派的人咧？只需要确定自己的队长是谁就好了，这时find函数就派上用场了：

int find(int x) //查找根结点（队长）
{
    while(x != pre[x]) //我的上级不是队长
        x = pre[x];
    return x;//返回队长
}

大诗仙李白听说这消息很是激动，拜师学剑，数载学成归来，约了武林高手花木LAN与荆轲二人商讨组建一个帮派，于是花木LAN和荆轲两人到处拉人。于是形成了“李白帮派”：

达摩本拜橘右京为师，组成帮派，可是达摩跟花木兰成为了好朋友。本来橘右京跟李白打得死去活来，风云搅动，这样一来，京京不得不停手：“现在我们是朋友，不打了不打了。”李白也甚是欢喜，但是话锋一转，道：“好吧，现在我是你的上级。”橘右京不乐意哩，说：“我靠，凭啥呀？”于是两人再次打了起来。
因为我们并不关心李白是上级还是京京是上级，反正有个队长就好了。
我们就需要one函数来实现这个功能：

void join(int x, int y) //达摩、花木兰是朋友
{
    int a, b;
    a = find(x);//队长是李白
    b = find(y);//老大是京京
    if(x != y)
        pre[a] = b; //麻烦京京甘败下风吧
}

那么帮派就确定了：

一日荆轲要与达摩决战。可是彼此不分敌友啊~。

未完待续。

队长

并查集超强解析

前言

正文