这是一篇

并查集教学

[问题描述]

在frc赛场上,所有队伍都会和其他队伍建立友谊,这一层友谊可以让他们很轻松的向其他队伍借到零件。现在,我们场上有很多支队伍(n<10000),他们之间建立了复杂的友谊关系。现在问你其中一支队伍可不可以通过一条友谊链向另一支特定队伍借到零件。如A队与B队建立了友谊,B队与C队建立了友谊。那么,A队就可以通过B队向C队借到零件。

这个问题的一种朴素解决方案就是建一个图,每个队伍在图中抽象成一个点,若两支队伍建立了友谊,则在象征着两支队伍的两点之间连一条边。若询问两个队伍能否借到零件,就任选一支队伍,遍历能到达的所有的店,如果所有的点中有另一支队伍,就代表可以借到零件。若没有可以到就代表借不到零件。代码如下:

建图:

struct point{

    int path_n;//代表从这个点进出路径的数量

int path[10000];//这个点可以到达的具体的点

};

point[10000];

连线:

void add(int a,int b){//add(a,b)代表在a,b两个点之间连一条线

    point[a].path[point[a].path_n++]=b;

    point[b].path[point[b].path_n++]=a;

}

遍历:

bool flag[10000];//初始化为false,代表是否遍历到过这个点,防止死循环

bool dfs(int a,int b,int now){//dfs(a,b,now)代表询问从a点检查到b点是否连通,now代表现在遍历到的点,初次调用时赋值为a。

    flag [now]=true;//现在来过这个点了

    if (now==b)

             return true;//现在这个点就是b点了

    for (int i=1;i<=now.path_n;++i){//遍历now出来的所有路径

             if (!flag[now.path[i]]){//如果之前没有来过那个点,就尝试一下

                     if (dfs(a,b,now.path[i])==true)//从path[i]可以走到b点

                              return true;

             }

    }

    return false;//从now点到不了b点

}

但是,这个方法的时间复杂度可以分析一下,见图O(1),遍历O(n^2),而且空间都不一定够用。这时就可以用一个数据结构:并查集。

并查集是许许多多个抽象成树的集合,集合内的点是有联系的,即其中任意一个点代表的队伍都可以向任意一支其他队伍接到零件。如果用树来实现的话,那就是一棵树内所有元素都是在同一集合内的。那么,怎么查询a,b两点是否在同一集合内,也就是同一棵树内呢?其实很简单,只要比较a,b两点的根节点是否相同就可以了。另一个关键的问题就是怎么将a,b两棵树建立友谊也就是合并两个集合?也并不难,只要将a的根节点成为b的根节点的一个叶子节点就可以了。其时间复杂度不管查询还是构建都是O(1)。具体代码如下:

建立结构:(就是短短一句话)

int head[10000];//代表n支队伍抽象成的点,head[i]是i的父亲节点。初始化head[i]=i,代表他没有父亲节点,即是一个树的根。

联系:

int find_father(int i){//寻找i这棵树的根节点

    if (head[i]==i)//如果i是根节点

             return i;//返回i

    else head[i]=find_father(head[i]);//否则将head[i]直接改为i的根节点。

    return head[i];//返回根节点。

}

这里用了一个状态压缩的小技巧,把寻找根节点时遍历到的点的父亲都变为其根节点,方便下一次查询。

int unite(int a,int b){//合并a,b两棵树

    head[find_father(a)]=find_father(b);//将a的根节点变成b的根节点的一个叶子节点。

}

查询:

bool is_same_tree(int a,int b){//查询a,b是否在同一棵树内

    if (find_father(a)==find_father(b))//如果a,b的根节点相同即在同一棵树下

             return true;

             else return false;

}