并查集(wwwlehu6.vip乐虎官网Java达成)

并查集:基本

思路

数组里存的数字代表所属的聚合。比如arr[4]wwwlehu6.vip乐虎官网,==一;代表四是首先组。假诺arr[7]==一,代表柒也是首先组。既然
arr[4] == arr[7] == 一 ,那么申明肆 和 柒同属于二个凑合,

例子

先初步化三个数组。开头时数组内的值与数组的下角标一致。即各种数字都自创立1个小组。

0属于第0个小组(集合),1属于第1个小组(集合),2属于第2个小组(集合)……….

接下去让几个数字实行联合操作,便是组成代表队的进度(合并集合)。合并函数unionElements()介绍:

起头意况如下:

wwwlehu6.vip乐虎官网 1


5和陆进展组成代表队。5里的值就改成陆了。含义正是:5放弃了第陆小组,参与到了第4小组。伍和六属于第6小组。

wwwlehu6.vip乐虎官网 2

接下去 让一 和贰 实行组成代表队。一的下角标就变为二了。含义便是:1和二都属于第二小组。

wwwlehu6.vip乐虎官网 3

接下去让 2三开展组成代表队:二想和3开始展览组成代表队,二就带着原来的具备队友,参预到了三所在的武装力量。看上面arr[1]
== arr[2]==arr[3]==三,意思正是一 2 3 都属于第三小组。

wwwlehu6.vip乐虎官网 4

接下去 一 和
4 进行组成代表队:一就带着原来拥有的队友一起投入到4所在的军事中了。看下边arr[1]
== arr[2]==arr[3]==arr[4]==四,意思正是1 二 三 4都属于第陆小组。

wwwlehu6.vip乐虎官网 5

接下去1 和
5进行组成代表队:壹就带着原来拥有的队友壹起加入到5所在的大军中。伍在哪个部队吧? 因为arr[5]==陆,所以伍在第4小组。一就带着独具队友进入了小组陆。

看下面arr[1] ==
arr[2]==arr[3]==arr[4]==arr[5]==arr[6]==陆,意思便是壹 二 3 4 5
6都属于第陆小组。

 wwwlehu6.vip乐虎官网 6

 将以此例子的并查集用树形表示来,如下图所示:

wwwlehu6.vip乐虎官网 7

 

find()函数介绍:怎么求出四属于哪个集合呢,调用find(四)就好了。find(四)再次来到的结果是怎样吧,其实正是arr[4],也就是6,表示4属于第6小组。

 

isConnected函数介绍:

认清一和6是还是不是队友(1 和
陆 是否属于同四个汇集):arr[1]==arr[6]可以,是队友(属于同三个集结)

判定一和八是还是不是队友(1 和 8 是还是不是属于同1个集合):arr[1] !=
arr[8]可见,不是队友(不属于同三个相会)

 

代码

/**
 * 数组实现并查集,元素内数字代表集合号
 */
public class UnionFind {
    /**
     * 数组,表示并查集所有元素
     */
    private int[] id;

    /**
     * 并查集的元素个数
     */
    private int size;

    /**
     * 构造一个新的并查集
     *
     * @param size 初始大小
     */
    public UnionFind(int size) {
        //初始化个数
        this.size = size;
        //初始化数组,每个并查集都指向自己
        id = new int[size];
        for (int i = 0; i < size; i++) {
            id[i] = i;
        }
    }

    /**
     * 查看元素所属于哪个集合
     *
     * @param element 要查看的元素
     * @return element元素所在的集合
     */
    private int find(int element) {
        return id[element];
    }

    /**
     * 判断两个元素是否同属于一个集合
     *
     * @param firstElement  第一个元素
     * @param secondElement 第二个元素
     * @return <code>boolean</code> 如果是则返回true。
     */
    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }

    /**
     * 合并两个元素所在的集合,也就是连接两个元素
     *
     * @param firstElement  第一个元素
     * @param secondElement 第二个元素
     */
    public void unionElements(int firstElement, int secondElement) {
        //找出firstElement所在的集合
        int firstUnion = find(firstElement);
        //找出secondElement所在的集合
        int secondUnion = find(secondElement);

        //如果这两个不是同一个集合,那么合并。
        if (firstUnion != secondUnion) {
            //遍历数组,使原来的firstUnion、secondUnion合并为secondUnion
            for (int i = 0; i < this.size; i++) {
                if (id[i] == firstUnion) {
                    id[i] = secondUnion;
                }
            }
        }
    }

    /**
     * 本并查集使用数组实现,为了更直观地看清内部数据,采用打印数组
     */
    private void printArr() {
        for (int id : this.id) {
            System.out.print(id + "\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 10;
        UnionFind union = new UnionFind(n);
        System.out.println("初始:");
        union.printArr();

        System.out.println("连接了5 6");
        union.unionElements(5, 6);
        union.printArr();

        System.out.println("连接了1 2");
        union.unionElements(1, 2);
        union.printArr();

        System.out.println("连接了2 3");
        union.unionElements(2, 3);
        union.printArr();

        System.out.println("连接了1 4");
        union.unionElements(1, 4);
        union.printArr();

        System.out.println("连接了1 5");
        union.unionElements(1, 5);
        union.printArr();

        System.out.println("1  6 是否连接:" + union.isConnected(1, 6));

        System.out.println("1  8 是否连接:" + union.isConnected(1, 8));
    }
}

  

并查集:快速Union,慢Find

上边基本的并查集中,数组里存的始末正是温馨所在的小组号,大概能够通晓为当前小组的队长号。

上边情状的结尾一张图纸中。成分一和要素五组成代表队,那么就供给成分1所在军队的拥有成员都把本身的小组号改为新的小组号。伪代码如下:

for (int i = 0; i < 数组size; i++) {
    if (是否和元素1同属于队伍4) {
        id[i] = secondUnion;//改为新的队伍号
    }
}  

那般的联结操作太低效了,合并3遍就O(n)。所以选取飞快Union方式。

思路

原本的数组中存的是小组号(只怕队长的编号),而未来数组中存的是本人的‘三弟’的号码。(应该说是老爸结点,和阿爹数组,但为了更形象,依然叫‘堂哥’更好驾驭)。

各样成分都能够去认3个小弟去维护本身,幸免被欺悔。只好认1个三弟…不可能认多少个

例子

始发情形如下:各类成分里的剧情就是上下一心的下角标(编号)。表示本人就是和谐大哥,表示很随便,不从属于任何人。如下图所示

wwwlehu6.vip乐虎官网 8

连天5  陆  :
后来五号总是受凌虐,认六号为堂哥,本人的始末就成为6了。如下图所示

wwwlehu6.vip乐虎官网 9

老是1
二:后来1号发现自身单着也非常,认2号为大哥,自个儿的剧情就变成二了。如下图所示wwwlehu6.vip乐虎官网 10

连天贰 三:后来二号发现自身能力有限,就投奔了三号。

解读一下数组内的意思:arr[1]==2,表示成分一的三弟是二号;arr[2]==三,表示成分二的长兄是三号。所以成分①的老大哥其实是三号。

wwwlehu6.vip乐虎官网 11

连接1和4:一号想和四号成为3个小组,如何做吧?只供给让祥和的‘最终老四弟’出席到四号所在的小组就行了。所以一号就撮合自身的‘最后老大’3号,让三号认四号为堂哥。(四号是怎样来头呢?4号是四号的‘最后老大’,四号团结正是投机的末梢老大)。从此1
二 三 四那一个要素都是阖家了。

wwwlehu6.vip乐虎官网 12

地点那个处境其实用树形结构意味着就越发形象了:

接二连三一 和 四就是把1所在的根指向四。

wwwlehu6.vip乐虎官网 13

 连接一 伍: 一号想和5号成为贰个小组,如何是好呢?只需求让祥和的‘最终老二哥’加入到五号所在的小组就行了。所以一号就撮合自身的‘最终老大’肆号,让四号认陆号为大哥。(6号是什么来头呢?六号是五号的‘最后老大’)。如下图所示。从此1
二 三 四 5
陆那几个要素都是全亲朋好友了。wwwlehu6.vip乐虎官网 14

 

find()函数介绍:find函数正是找四弟的函数。怎么求出肆属于哪个集合呢,调用find(一)就好了。find(一)重临的结果是哪些啊,其实正是一的‘最后大哥’ 成分四。详细进度见代码。

 

isConnected函数介绍:

判定一和6是否队友(壹 和
六 是还是不是属于同一个会晤):find(一) 是否等于 find(6),也正是 判断俩成分是或不是是同1个‘最后表哥’

判定1和八是还是不是队友(一 和
八 是还是不是属于同一个集合):find(一) 是还是不是等于 find(6),也正是 判断俩成分是不是是同二个‘最终大哥’

代码

/**
 * 数组模拟树,实现并查集。数组内的元素表示父亲的下角表,相当于指针。
 */
public class UnionFind {
    private int[] parent;
    private int size;

    public UnionFind(int size) {
        this.size = size;
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    public int find(int element) {
        while (element != parent[element]) {
            element = parent[element];
        }
        return element;
    }

    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }

    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
        if (firstRoot == secondRoot) {
            return;
        }
        parent[firstRoot] = secondRoot;
    }

    /**
     * 本并查集使用数组实现,为了更直观地看清内部数据,采用打印数组
     */
    private void printArr() {
        for (int parent : this.parent) {
            System.out.print(parent + "\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 10;
        UnionFind union = new UnionFind(n);
        System.out.println("初始:");
        union.printArr();

        System.out.println("连接了5 6");
        union.unionElements(5, 6);
        union.printArr();

        System.out.println("连接了1 2");
        union.unionElements(1, 2);
        union.printArr();

        System.out.println("连接了2 3");
        union.unionElements(2, 3);
        union.printArr();

        System.out.println("连接了1 4");
        union.unionElements(1, 4);
        union.printArr();

        System.out.println("连接了1 5");
        union.unionElements(1, 5);
        union.printArr();

        System.out.println("1  6 是否连接:" + union.isConnected(1, 6));

        System.out.println("1  8 是否连接:" + union.isConnected(1, 8));
    }
}

  

并查集:急速union,急速find,基于重量

思路和例子

其实下边讲的union函数,未有应用有理的招数去开始展览统一。每便都是secondElement为主,每一趟合并五个聚众都让secondElement的根来继承担纲联合之后的根。那样很只怕达到线性的链表的图景。

那合并的时候怎么处理更行吗?

比如:有上边几个集聚。当中 贰 和
陆 是多个聚众的根。上边要让那七个聚众合并,然而,合并之后只好有二个十三分啊,到底何人来当呢?

在遵照重量的union里,何人的人手多,就由哪个人来当合并之后的表弟。

二成分有四个手下,再算上团结,这正是7人。

六成分有2个手下,再算上协调,那正是三位。

很明显是二成分的人士多,所以2来充当联合之后的根节点。

wwwlehu6.vip乐虎官网 15

代码

public class UnionFind {
    private int[] parent;
    private int[] weight;
    private int size;

    public UnionFind(int size) {
        this.parent = new int[size];
        this.weight = new int[size];
        this.size = size;
        for (int i = 0; i < size; i++) {
            this.parent[i] = i;
            this.weight[i] = 1;
        }
    }

    public int find(int element) {
        while (element != parent[element]) {
            element = parent[element];
        }
        return element;
    }

    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }

    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);

        //如果已经属于同一个集合了,就不用再合并了。
        if (firstRoot == secondRoot) {
            return;
        }

        if (weight[firstRoot] > weight[secondRoot]) {
            parent[secondRoot] = firstRoot;
            weight[firstRoot] += weight[secondRoot];
        } else {//weight[firstRoot] <= weight[secondRoot]
            parent[firstRoot] = secondRoot;
            weight[secondRoot] += weight[firstRoot];
        }
    }

    private void printArr(int[] arr){
        for(int p : arr){
            System.out.print(p+"\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 10;
        UnionFind union = new UnionFind(n);

        System.out.println("初始parent:");
        union.printArr(union.parent);
        System.out.println("初始weight:");
        union.printArr(union.weight);

        System.out.println("连接了5 6 之后的parent:");
        union.unionElements(5, 6);
        union.printArr(union.parent);
        System.out.println("连接了5 6 之后的weight:");
        union.printArr(union.weight);

        System.out.println("连接了1 2 之后的parent:");
        union.unionElements(1, 2);
        union.printArr(union.parent);
        System.out.println("连接了1 2 之后的weight:");
        union.printArr(union.weight);

        System.out.println("连接了2 3 之后的parent:");
        union.unionElements(2, 3);
        union.printArr(union.parent);
        System.out.println("连接了2 3 之后的weight:");
        union.printArr(union.weight);

        System.out.println("连接了1 4 之后的parent:");
        union.unionElements(1, 4);
        union.printArr(union.parent);
        System.out.println("连接了1 4 之后的weight:");
        union.printArr(union.weight);

        System.out.println("连接了1 5 之后的parent:");
        union.unionElements(1, 5);
        union.printArr(union.parent);
        System.out.println("连接了1 5 之后的weight:");
        union.printArr(union.weight);

        System.out.println("1  6 是否连接:" + union.isConnected(1, 6));

        System.out.println("1  8 是否连接:" + union.isConnected(1, 8));
    }
}

并查集:飞速union,快速find,基于中度(基于秩)

思路

地方介绍的是,当多少个聚众合并时,哪个人的份额大,什么人就来当合并之后的根。是比原先好多了。但要么有并查集深度太深的题材。并查集越深,就越接近线性,find函数就越接近O(n)

所以有了那种基于中度的union。合并时,何人的深浅深,何人正是新的根。这样集合的纵深最多是最大深度的会见的深度,而不会让深度扩展。

譬如说上面的事例中,成分2的深度是二,成分六的吃水是叁,按基于重量的union合并后,新的成团深度是四。

只是假如比不上重量,而是比高度呢?

这便是陆的深浅是三,二的深浅是2。3大于二,
所以6是新集合的根。看上面图。 能够看出按中度统一后,新的整合的吃水并不曾加深,深度为三,而按基于重量的集合后的惊人是肆。

wwwlehu6.vip乐虎官网 16

 

别的的地点与前面类似,只是我们可能对这段代码有疑惑。作者来画个图讲解一下。

        if (height[firstRoot] < height[secondRoot]) {
            parent[firstRoot] = secondRoot;
        } else if (height[firstRoot] > height[secondRoot]) {
            parent[secondRoot] = firstRoot;
        } else {
            parent[firstRoot] = secondRoot;
            height[secondRoot] += 1;
        }  

代码中的if 和 else if三种景况应该好明白。七个集聚的莫斯中国科学技术大学学分化等的时候,对它们进行统1,新集合高度肯定齐名中度大的特别集合的可观。所以中度不用调整。

而三个汇聚中度相等时,哪个根来当新集合的根已经漠不关怀了,只需求让里面一个对准另1个就好了。然后会意识深度加了1层,所以新集合的根的中度就得+一,看上面图。

wwwlehu6.vip乐虎官网 17

代码

public class UnionFind {
    private int[] parent;
    private int[] height;
    int size;

    public UnionFind(int size) {
        this.size = size;
        this.parent = new int[size];
        this.height = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            height[i] = 1;
        }
    }

    public int find(int element) {
        while (element != parent[element]) {
            element = parent[element];
        }
        return element;
    }

    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }

    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);

        if (height[firstRoot] < height[secondRoot]) {
            parent[firstRoot] = secondRoot;
        } else if (height[firstRoot] > height[secondRoot]) {
            parent[secondRoot] = firstRoot;
        } else {
            parent[firstRoot] = secondRoot;
            height[secondRoot] += 1;
        }
    }

                /*
              如果要合并的两个集合高度一样,那么随意选一个作为根
              我这里选的是让secondRoot作为新集合的根。
              然后secondRoot高度高了一层,所以+1
            */

    private void printArr(int[] arr){
        for(int p : arr){
            System.out.print(p+"\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 10;
        UnionFind union = new UnionFind(n);

        System.out.println("初始parent:");
        union.printArr(union.parent);
        System.out.println("初始height:");
        union.printArr(union.height);

        System.out.println("连接了5 6 之后的parent:");
        union.unionElements(5, 6);
        union.printArr(union.parent);
        System.out.println("连接了5 6 之后的height:");
        union.printArr(union.height);

        System.out.println("连接了1 2 之后的parent:");
        union.unionElements(1, 2);
        union.printArr(union.parent);
        System.out.println("连接了1 2 之后的height:");
        union.printArr(union.height);

        System.out.println("连接了2 3 之后的parent:");
        union.unionElements(2, 3);
        union.printArr(union.parent);
        System.out.println("连接了2 3 之后的height:");
        union.printArr(union.height);

        System.out.println("连接了1 4 之后的parent:");
        union.unionElements(1, 4);
        union.printArr(union.parent);
        System.out.println("连接了1 4 之后的height:");
        union.printArr(union.height);

        System.out.println("连接了1 5 之后的parent:");
        union.unionElements(1, 5);
        union.printArr(union.parent);
        System.out.println("连接了1 5 之后的height:");
        union.printArr(union.height);

        System.out.println("1  6 是否连接:" + union.isConnected(1, 6));

        System.out.println("1  8 是否连接:" + union.isConnected(1, 8));
    }
}

  

并查集优化:路径压缩

思路

路线压缩正是拍卖并查集中的深的结点。达成格局很简短,正是在find函数里丰硕一句 parent[element]

parent[parent[element]];就好了,便是让近期结点指向自身生父的阿爸,收缩深度,同时还尚未改变根结点的weight(非根节点的weight改变了无视)。

注:只可以在依照重量的并查集上改find函数,而不可能在依据高度的并查集上采取那种路径压缩。因为路径压缩后根的份额不变,但可观会变,不过中度改变后又不便宜重新总括。

代码

public class UnionFind {
    private int[] parent;
    private int[] weight;
    private int size;

    public UnionFind(int size) {
        this.parent = new int[size];
        this.weight = new int[size];
        this.size = size;
        for (int i = 0; i < size; i++) {
            this.parent[i] = i;
            this.weight[i] = 1;
        }
    }

    public int find(int element) {
        while (element != parent[element]) {
            parent[element] = parent[parent[element]];
            element = parent[element];
        }
        return element;
    }

    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }

    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);

        //如果已经属于同一个集合了,就不用再合并了。
        if (firstRoot == secondRoot) {
            return;
        }

        if (weight[firstRoot] > weight[secondRoot]) {
            parent[secondRoot] = firstRoot;
            weight[firstRoot] += weight[secondRoot];
        } else {//weight[firstRoot] <= weight[secondRoot]
            parent[firstRoot] = secondRoot;
            weight[secondRoot] += weight[firstRoot];
        }
    }

    private void printArr(int[] arr){
        for(int p : arr){
            System.out.print(p+"\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 10;
        UnionFind union = new UnionFind(n);

        System.out.println("初始parent:");
        union.printArr(union.parent);
        System.out.println("初始weight:");
        union.printArr(union.weight);

        System.out.println("连接了5 6 之后的parent:");
        union.unionElements(5, 6);
        union.printArr(union.parent);
        System.out.println("连接了5 6 之后的weight:");
        union.printArr(union.weight);

        System.out.println("连接了1 2 之后的parent:");
        union.unionElements(1, 2);
        union.printArr(union.parent);
        System.out.println("连接了1 2 之后的weight:");
        union.printArr(union.weight);

        System.out.println("连接了2 3 之后的parent:");
        union.unionElements(2, 3);
        union.printArr(union.parent);
        System.out.println("连接了2 3 之后的weight:");
        union.printArr(union.weight);

        System.out.println("连接了1 4 之后的parent:");
        union.unionElements(1, 4);
        union.printArr(union.parent);
        System.out.println("连接了1 4 之后的weight:");
        union.printArr(union.weight);

        System.out.println("连接了1 5 之后的parent:");
        union.unionElements(1, 5);
        union.printArr(union.parent);
        System.out.println("连接了1 5 之后的weight:");
        union.printArr(union.weight);

        System.out.println("1  6 是否连接:" + union.isConnected(1, 6));

        System.out.println("1  8 是否连接:" + union.isConnected(1, 8));
    }
}

  

连锁练习题

杭电ACM-1213-How Many Tables

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1213

Today is Ignatius’ birthday. He invites a lot of friends. Now it’s
dinner time. Ignatius wants to know how many tables he needs at least.
You have to notice that not all the friends know each other, and all
the friends do not want to stay with strangers.

One important rule for this problem is that if I tell you A knows B,
and B knows C, that means A, B, C know each other, so they can stay in
one table.

For example: If I tell you A knows B, B knows C, and D knows E, so A,
B, C can stay in one table, and D, E have to stay in the other one. So
Ignatius needs 2 tables at least.

翻译:要坐在桌子上吃饭,可是人们拒绝和素不相识人坐在一张桌子上。什么样的不算目生人呢?首若是情人的爱侣的爱侣的…..只要能扯上关系就不算面生人。能扯上提到就能够坐在一张桌子上。所以至少要准备多少张桌子?

 

思路:其实正是对并查集进行合并操作,只要俩人认识,就组成代表队。把队组好以往,看最后有多少个组(集合)就行了。最初每种人都自成壹组,所以有微微人就有微微组。不过随着他们组成代表队,每多个结合并成2个组,总的组数就会少一。假若组成代表队的时候发现,他俩已经早就‘扯上涉及了’,也就表名他俩早正是一组了,那就毫无继续联合了,也就绝不再
-1 了。

代码:

class UnionFind {
    private int[] parent;
    private int[] weight;
    private int size;//代表并查集中元素个数
    private int groups;//代表并查集中有多少个集合(小组)

    public UnionFind(int size) {
        this.parent = new int[size];
        this.weight = new int[size];
        this.size = size;
        this.groups = size;//因为初始的时候每个人自成一组,所以有多少人就有多少组
        for (int i = 0; i < size; i++) {
            this.parent[i] = i;
            this.weight[i] = 1;
        }
    }

    public int find(int element) {
        while (element != parent[element]) {
            parent[element] = parent[parent[element]];
            element = parent[element];
        }
        return element;
    }

    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }

    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);

        //如果已经属于同一个集合了,就不用再合并了。
        if (firstRoot == secondRoot) {
            return;
        }

        if (weight[firstRoot] > weight[secondRoot]) {
            parent[secondRoot] = firstRoot;
            weight[firstRoot] += weight[secondRoot];
        } else {//weight[firstRoot] <= weight[secondRoot]
            parent[firstRoot] = secondRoot;
            weight[secondRoot] += weight[firstRoot];
        }

        //合并 firstElement 和 secondElement 所在的两个组后,就少了一组。
        this.groups--;
    }

    public int getGroups() {
        return this.groups;
    }
}

public class Main {
    public static void main(String[] args) {
        java.util.Scanner scanner = new java.util.Scanner(System.in);
        int times = scanner.nextInt();
        for (int i = 0; i < times; i++) {
            int size = scanner.nextInt();
            UnionFind union = new UnionFind(size);
            int input = scanner.nextInt();
            for (int j = 0; j < input; j++) {
                //因为测试数据是从1开始,而我们的并查集是从数组的第0位开始
                int first = scanner.nextInt() - 1;
                int second = scanner.nextInt() - 1;
                union.unionElements(first, second);
            }
            System.out.println(union.getGroups());
        }
    }
}  

杭电ACM-123二-畅通工程

连接:http://acm.hdu.edu.cn/showproblem.php?pid=1232

某省调查城市和市场交通境况,得到现有城市和市场征程计算表,表中列出了每条道路一直连接的商场。省府“畅通工程”的指标是使全省别的两个村镇间都足以达成畅通(但不必然有一贯的道路相连,只要相互间接通过道路可达即可)。问最少还亟需建设多少条道路? 

思路:与地方题思路壹致,在并查集中开始展览联合操作,求出最终剩余多少个组(集合)。那一个组之间是互相不可达的。即便有M个组,那实在再须求M-一条连线就能够把他们连接起来了。所以组数

  • 1 正是终极答案

代码:

class UnionFind {
    /**
     * 记录并查集对应位置的父亲结点位置
     */
    private int[] parent;
    /**
     * 记录并查集对应结点的重量
     */
    private int[] weight;
    /**
     * 表示并查集的元素个数
     */
    private int size;
    /**
     * 表示并查集中集合的个数(组数)
     */
    private int groups;

    public UnionFind(int size) {
        this.size = size;
        this.groups = size;
        this.parent = new int[size];
        this.weight = new int[size];
        for (int i = 0; i < size; i++) {
            this.parent[i] = i;
            this.weight[1] = 1;
        }
    }

    public int find(int element) {
        while (element != parent[element]) {
            parent[element] = parent[parent[element]];
            element = parent[element];
        }
        return element;
    }

    public boolean isConneted(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }

    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
        if (firstRoot == secondRoot) {
            return;
        }
        if (weight[firstRoot] < weight[secondRoot]) {
            parent[firstRoot] = secondRoot;
            weight[secondRoot] += weight[firstRoot];
        } else {
            parent[secondRoot] = firstRoot;
            weight[firstRoot] += secondRoot;
        }

        this.groups--;
    }

    public int getGroups(){
        return this.groups;
    }
}

public class Main {
    public static void main(String[] args) {
        java.util.Scanner scanner = new java.util.Scanner(System.in);
        int size = scanner.nextInt();
        while(size!=0){
            int input = scanner.nextInt();
            UnionFind union = new UnionFind(size);
            for(int i = 0;i<input;i++){
                //因为测试数据中是从1开始技术。而我们的并查集是从0开始,所以每个输入都减1
                int first = scanner.nextInt() - 1;
                int second = scanner.nextInt() - 1;
                union.unionElements(first,second);
            }
            //最后剩下的组数 - 1 就是最后的答案。因为连接M组的话,需要M-1条连线就可以了
            System.out.println(union.getGroups() - 1);
            size = scanner.nextInt();
        }
    }
}

  

You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图