美文网首页
2018-11-27 并查集

2018-11-27 并查集

作者: 我的的昵称已被使用换一个吧 | 来源:发表于2018-11-27 18:27 被阅读0次

    并查集:合并、查找、集合

    问题:小希的迷宫:

    Description

    上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从 5到达8。

    Input

    输入包含多组数据,每组数据是一个以0

    0结尾的整数对列表,表示了一条通道连接的两个房间的编号。房间的编号至少为1,且不超过100000。每两组数据之间有一个空行。整个文件以两个-1结尾。

    Output

    对于输入的每一组数据,输出仅包括一行。如果该迷宫符合小希的思路,那么输出"Yes",否则输出"No"。

    Sample Input

    6 8  5 3  5 2  6 4

    5 6  0 0

    8 1  7 3  6 2  8 9  7 5

    7 4  7 8  7 6  0 0

    3 8  6 8  6 4

    5 3  5 6  5 2  0 0

    -1 -1

    Sample Output

    Yes

    Yes

    No

    首先有许多离散的点,刚开始他们都没有联系,所以,他们的父节点就是他们自己

    for (int i = 0; i < room.length; i++) {

    father[i]=i;//刚开始还没构建树父节点都是自己

    vis[i]=0;

    }

    private static void merge(int a, int b) {

    // TODO Auto-generated method stub

        int A,B;

        A=find(a);        //查找父节点

        B=find(b);

            //若父节点相同则一定属于一个集合

        if(A!=B)

        {

            father[B]=A;    //父节点不同则,要放到一个集合里面

        }

        else

        {

            ok=0;

        }

    }

    核心

    find:

    递归路径压缩)

    递归对栈空间要求比较高,若数据量较大则不能满足时间要求

    find 主要目的就是找x的根节点,那么x的根节点怎么找呢?

    看x的上一级是否等于x,若相等则说明x的根节点就是本身那么返回pre[x]就好(因为最开头的初始化数组)

    若不等于,则,x的上一级再去寻找直到相等

    //循环路径压缩

    以第一个图为例

    刚开始进行初始化

    每个父节点都是他们自己所以father数组为

    father[0 1 2 3 4 5 6 7 8 9 10 11 12...........]

    然后进入merge函数进行集合的归并

    假设输入6、8和8、2

    进入find

    father[6]==6

    返回6

    8也同理

    然后返回到merge

    A=6;

    B=8;

    6!=8

    father[8]=6;    //表明8跟6 有关系  8的父节点是6

    然后再看8、2

    此时father[8]!=8

    所以进行查找父节点

    r = father[8]=6

    father[6]=6

    进入第二次循环直至循环根节点

    8!=6

    j=father[8]=6

    father[8]=r=6

    i=6

    6==6

    A=6

    2就是2

    B=2

    father[2]=6 //代表2跟6有联系

    那这样6 8 2就有了关系

    (第一个循环是找到父节点,第二个循环是进行路径压缩)

    private static int find(int a) {

    // TODO Auto-generated method stub

        int r=a;

        while(father[r]!=r)

        r=father[r];

        int i=a;

        int j;

        while(i!=r)

        {

            j=father[i];

            father[i]=r;

            i=j;

        }

        return r;

    }

    路径压缩(其实就是减少查找的复杂度)

    相关文章

      网友评论

          本文标题:2018-11-27 并查集

          本文链接:https://www.haomeiwen.com/subject/zangqqtx.html