本文概览：介绍了解决并查集问题三个步骤。

1 并查集问题方案

用于处理不相交集合的合并和查询问题，速度很快。

并查集需要提供三个基本方法：

初始化每个节点的根节点信息data[i]=i。 init(n)
查找一个节点的根节点。 find(x)
合并两个节点的根节点。 merge(x,y)

并发集相关问题方法论：

STEP1 : 初始化并查集。使用init(n)

STEP1 : 扫描一遍输入生成并查集。使用merge（x,y）方法创建。

STEP2：根据并查集生成结果。使用find（x）

模板代码如下：

mereg，合并两个节点的根节点为同一个节点根节点。

/**
 * Map.Entry
 * ---------
 * 并查集相关问题解题模型:
 * 准备: 构建三个基本方法
 * STEP1 并查集构建。通过上面基本方法构建
 * STEP2 并查集使用
 */
public class UionFind {
    // 保存每一个节点的根节点:
    // 这样只要捞取data[i]==i的节点就知道有几个集合了
    List<Integer> data = new ArrayList<Integer>();


    public void init(int n) {
        for (int i = 0; i < n; i++) {
            data.add(i);
        }
    }

    /**
     * 依次查询当前节点的根节点
     *
     * @param index
     * @return
     */
    public int find(int index) {
        if (data.get(index) == index) {
            return index;
        } else {
            return find(data.get(index));
        }
    }

    /**
     * 合并两个节点的根节点为同一个节点根节点
     */
    public void merge(int union1, int union2) {

        int r1 = find(union1);
        int r2 = find(union2);

        if (r1 == r2) {
            return;
        }
        data.set(r1, r2);
    }

    // 业务代码
    public void process(List<List<String>> input) {

        // STEP1：初始化并查集 

        // STEP2 创建并查集 

        // STEP3 根据并查集输出结果

    }
}

/**

* Map.Entry

* ---------

* 并查集相关问题解题模型:

* 准备: 构建三个基本方法

* STEP1 并查集构建。通过上面基本方法构建

* STEP2 并查集使用

public class UionFind {

// 保存每一个节点的根节点:

// 这样只要捞取data[i]==i的节点就知道有几个集合了

List<Integer> data = new ArrayList<Integer>();

public void init(int n) {

for (int i = 0; i < n; i++) {

data.add(i);

}

/**

* 依次查询当前节点的根节点

* @param index

* @return

public int find(int index) {

if (data.get(index) == index) {

return index;

} else {

return find(data.get(index));

}

/**

* 合并两个节点的根节点为同一个节点根节点

public void merge(int union1, int union2) {

int r1 = find(union1);

int r2 = find(union2);

if (r1 == r2) {

return;

}

data.set(r1, r2);

}

// 业务代码

public void process(List<List<String>> input) {

// STEP1：初始化并查集

// STEP2 创建并查集

// STEP3 根据并查集输出结果

}

2 实例

2.1 邮箱问题

如下每个用户有多个邮箱，邮箱是唯一的，但是多个用户，可能用户名是相同，现在给了一组用户名和邮箱关系，需要找到每个用户对应的邮箱名。

参考：https://leetcode-cn.com/problems/accounts-merge/

input = [
["John", "johnsmith@mail.com", "john00@mail.com"], 
["John", "johnnybravo@mail.com"], 
["John", "johnsmith@mail.com", "john_newyork@mail.com"], 
["Mary", "mary@mail.com"]
]

Output: [
["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  
["John", "johnnybravo@mail.com"], 
["Mary", "mary@mail.com"]
]

input = [

["John", "johnsmith@mail.com", "john00@mail.com"],

["John", "johnnybravo@mail.com"],

["John", "johnsmith@mail.com", "john_newyork@mail.com"],

["Mary", "mary@mail.com"]

]

Output: [

["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],

["John", "johnnybravo@mail.com"],

["Mary", "mary@mail.com"]

]

算法

/**
 * Map.Entry
 * ---------
 * 并查集相关问题解题模型:
 * 准备: 构建三个基本方法
 * STEP1 并查集构建。通过上面基本方法构建
 * STEP2 并查集使用
 */
public class UionFind {
    // 保存每一个节点的根节点:
    // 这样只要捞取data[i]==i的节点就知道有几个集合了
    List<Integer> data = new ArrayList<Integer>();


    public void init(int n) {
        for (int i = 0; i < n; i++) {
            data.add(i);
        }
    }

    /**
     * 依次查询当前节点的根节点
     *
     * @param index
     * @return
     */
    public int find(int index) {
        if (data.get(index) == index) {
            return index;
        } else {
            return find(data.get(index));
        }
    }

    /**
     * 合并两个节点为同一个节点根节点
     */
    public void merge(int union1, int union2) {
        int r1 = find(union1);
        int r2 = find(union2);

        if (r1 == r2) {
            return;
        }
        data.set(r1, r2);
    }

    // 业务代码
    public void process(List<List<String>> input) {
        // STEP1.初始化并查集
        init(input.size());

        // 记录每一个邮箱信息
        Map<String, Integer> dic = new HashMap<String, Integer>();

        // STEP2 构建并查集
        for (int i = 0; i < input.size(); i++) {
            List<String> line = input.get(i);
            for (int j = 1; j < line.size(); j++) {
                if (dic.containsKey(line.get(j))) {
                    int union1 = dic.get(line.get(j));
                    merge(union1, i);
                } else {
                    dic.put(line.get(j), i);
                }
            }
        }


        // STEP3 应用并查集输出结果
        Map<Integer, HashSet<String>> result = new HashMap<Integer, HashSet<String>>();
        for (int i = 0; i < input.size(); i++) {
            int key = find(i);
            if (!result.containsKey(key)) {
                result.put(key, new HashSet<String>());
            }

            List<String> line = input.get(i);
            for (int j = 1; j < line.size(); j++) {
                result.get(key).add(line.get(j));
            }
        }


        List<List<String>> output = new ArrayList<List<String>>();
        for (Map.Entry<Integer, HashSet<String>> entry : result.entrySet()) {
            List<String> line = new ArrayList<String>();
            line.add(input.get(entry.getKey()).get(0));
            List<String> valueList = new ArrayList<String>(entry.getValue());
            Collections.sort(valueList);
            for (String email : valueList) {
                line.add(email);
            }
            output.add(line);
        }


        System.out.println(output);

    }

   
    public static void main(String[] args){
        List<List<String>> input = Lists.newArrayList();
        input.add(Lists.<String>newArrayList("John", "johnsmith@mail.com", "john00@mail.com"));
        input.add(Lists.<String>newArrayList("John", "johnnybravo@mail.com"));

        input.add(Lists.<String>newArrayList("John", "johnsmith@mail.com", "john_newyork@mail.com"));
        input.add(Lists.<String>newArrayList("Mary", "mary@mail.com"));
        UionFind uionFind = new UionFind();
        uionFind.process(input);

    }

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

/**

* Map.Entry

* ---------

* 并查集相关问题解题模型:

* 准备: 构建三个基本方法

* STEP1 并查集构建。通过上面基本方法构建

* STEP2 并查集使用

public class UionFind {

// 保存每一个节点的根节点:

// 这样只要捞取data[i]==i的节点就知道有几个集合了

List<Integer> data = new ArrayList<Integer>();

public void init(int n) {

for (int i = 0; i < n; i++) {

data.add(i);

}

/**

* 依次查询当前节点的根节点

* @param index

* @return

public int find(int index) {

if (data.get(index) == index) {

return index;

} else {

return find(data.get(index));

}

/**

* 合并两个节点为同一个节点根节点

public void merge(int union1, int union2) {

int r1 = find(union1);

int r2 = find(union2);

if (r1 == r2) {

return;

}

data.set(r1, r2);

}

// 业务代码

public void process(List<List<String>> input) {

// STEP1.初始化并查集

init(input.size());

// 记录每一个邮箱信息

Map<String, Integer> dic = new HashMap<String, Integer>();

// STEP2 构建并查集

for (int i = 0; i < input.size(); i++) {

List<String> line = input.get(i);

for (int j = 1; j < line.size(); j++) {

if (dic.containsKey(line.get(j))) {

int union1 = dic.get(line.get(j));

merge(union1, i);

} else {

dic.put(line.get(j), i);

}

// STEP3 应用并查集输出结果

Map<Integer, HashSet<String>> result = new HashMap<Integer, HashSet<String>>();

for (int i = 0; i < input.size(); i++) {

int key = find(i);

if (!result.containsKey(key)) {

result.put(key, new HashSet<String>());

}

List<String> line = input.get(i);

for (int j = 1; j < line.size(); j++) {

result.get(key).add(line.get(j));

}

List<List<String>> output = new ArrayList<List<String>>();

for (Map.Entry<Integer, HashSet<String>> entry : result.entrySet()) {

List<String> line = new ArrayList<String>();

line.add(input.get(entry.getKey()).get(0));

List<String> valueList = new ArrayList<String>(entry.getValue());

Collections.sort(valueList);

for (String email : valueList) {

line.add(email);

}

output.add(line);

}

System.out.println(output);

}

public static void main(String[] args){

List<List<String>> input = Lists.newArrayList();

input.add(Lists.<String>newArrayList("John", "johnsmith@mail.com", "john00@mail.com"));

input.add(Lists.<String>newArrayList("John", "johnnybravo@mail.com"));

input.add(Lists.<String>newArrayList("John", "johnsmith@mail.com", "john_newyork@mail.com"));

input.add(Lists.<String>newArrayList("Mary", "mary@mail.com"));

UionFind uionFind = new UionFind();

uionFind.process(input);

}

2.2 好友关系

假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友…），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。

假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。

算法

/**
 * Map.Entry
 * ---------
 * 并查集相关问题解题模型:
 * 准备: 构建三个基本方法
 * STEP1 并查集构建。通过上面基本方法构建
 * STEP2 并查集使用
 */
public class FriendFind {
    // 保存每一个节点的根节点:
    // 这样只要捞取data[i]==i的节点就知道有几个集合了
    List<Integer> data = new ArrayList<Integer>();


    public void init(int n) {
        for (int i = 0; i < n; i++) {
            data.add(i);
        }
    }

    /**
     * 依次查询当前节点的根节点
     *
     * @param index
     * @return
     */
    public int find(int index) {
        if (data.get(index) == index) {
            return index;
        } else {
            return find(data.get(index));
        }
    }

    /**
     * 合并两个节点为同一个节点根节点
     */
    public void merge(int union1, int union2) {
        int r1 = find(union1);
        int r2 = find(union2);

        if (r1 == r2) {
            return;
        }
        data.set(r1, r2);
    }

    public void process(List<List<Integer>> input) {
        // STEP1 初始化并查集
        init(6);

        // STEP2 构建并查集
        for (int i = 0; i < input.size(); i++) {
            List<Integer> res = input.get(i);
            merge(res.get(0),res.get(1));
        }

        // STEP3 使用并查集输出结果
        Map<Integer,Set<Integer>> result = new HashMap<Integer,Set<Integer>>();
        for(int i=1 ; i<data.size();i++){
            int key = find(i);
            if(!result.containsKey(key)){
                result.put(key,new HashSet<Integer>());
            }
            result.get(key).add(i);
        }

        System.out.printf(result.toString());


    }

    public static void main(String[] args) {
        List<List<Integer>> input = Lists.newArrayList();
        input.add(Lists.<Integer>newArrayList(1,2));
        input.add(Lists.<Integer>newArrayList(2,3));
        input.add(Lists.<Integer>newArrayList(4,5));

        FriendFind uionFind = new FriendFind();
        uionFind.process(input);

    }
}

/**

* Map.Entry

* ---------

* 并查集相关问题解题模型:

* 准备: 构建三个基本方法

* STEP1 并查集构建。通过上面基本方法构建

* STEP2 并查集使用

public class FriendFind {

// 保存每一个节点的根节点:

// 这样只要捞取data[i]==i的节点就知道有几个集合了

List<Integer> data = new ArrayList<Integer>();

public void init(int n) {

for (int i = 0; i < n; i++) {

data.add(i);

}

/**

* 依次查询当前节点的根节点

* @param index

* @return

public int find(int index) {

if (data.get(index) == index) {

return index;

} else {

return find(data.get(index));

}

/**

* 合并两个节点为同一个节点根节点

public void merge(int union1, int union2) {

int r1 = find(union1);

int r2 = find(union2);

if (r1 == r2) {

return;

}

data.set(r1, r2);

}

public void process(List<List<Integer>> input) {

// STEP1 初始化并查集

init(6);

// STEP2 构建并查集

for (int i = 0; i < input.size(); i++) {

List<Integer> res = input.get(i);

merge(res.get(0),res.get(1));

}

// STEP3 使用并查集输出结果

Map<Integer,Set<Integer>> result = new HashMap<Integer,Set<Integer>>();

for(int i=1 ; i<data.size();i++){

int key = find(i);

if(!result.containsKey(key)){

result.put(key,new HashSet<Integer>());

}

result.get(key).add(i);

}

System.out.printf(result.toString());

}

public static void main(String[] args) {

List<List<Integer>> input = Lists.newArrayList();

input.add(Lists.<Integer>newArrayList(1,2));

input.add(Lists.<Integer>newArrayList(2,3));

input.add(Lists.<Integer>newArrayList(4,5));

FriendFind uionFind = new FriendFind();

uionFind.process(input);

}

输出结果为：

{3=[1, 2, 3], 5=[4, 5]}

Heart.Think.Do

常用算法-并查集

1 并查集问题方案

2 实例

2.1 邮箱问题

2.2 好友关系

Related Posts:

分类&标签