并查集及其应用

发表于 | 分类于

题目一：并查集（算法课第七课）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.HashMap;
import java.util.List;

public class UnionFind {//头条201808825第一题
	public static class Node {
		// whatever you like
	}

	public static class UnionFindSet {// 小头挂大头
		public HashMap<Node, Node> fatherMap;// KEY:child,VALUE：father . 一路往上找父节点
		public HashMap<Node, Integer> sizeMap;// 某节点所在的集合一共多少节点

		public UnionFindSet(List<Node> nodes) {//一次性把所有样本 传入
			makeSets(nodes);
		}

		private void makeSets(List<Node> nodes) {
			fatherMap = new HashMap<Node, Node>();
			sizeMap = new HashMap<Node, Integer>();
			for (Node node : nodes) {//开始的时候每个节点，自成一个集合
				fatherMap.put(node, node);
				sizeMap.put(node, 1);
			}
		}
		//1. 找到代表节点 	2.把集合所有节点 直接链向代表节点 
		private Node findHead(Node node) {//找到 “代表节点”
			Node father = fatherMap.get(node);
			if (father != node) {//直到自己是自己爹（代表节点）
				father = findHead(father);
			}
			fatherMap.put(node, father);
			return father;
		}

		public boolean isSameSet(Node a, Node b) {
			return findHead(a) == findHead(b);//最终找到同一个源头，就是一个集合的
		}

		public void union(Node a, Node b) {
			if (a == null || b == null) {
				return;
			}
			Node aHead = findHead(a);
			Node bHead = findHead(b);
			if (aHead != bHead) { //不在一个集合 ，才需要合并
				int aSetSize = sizeMap.get(aHead);
				int bSetSize = sizeMap.get(bHead);
				if (aSetSize <= bSetSize) {//只用改变 1. 头 2. 集合大小
					fatherMap.put(aHead, bHead);
					sizeMap.put(bHead, aSetSize + bSetSize);
				} else {
					fatherMap.put(bHead, aHead);
					sizeMap.put(aHead, aSetSize + bSetSize);
				}
			}
		}

	}

	public static void main(String[] args) {
		//……
	}
}

题目二：朋友圈(头条笔试)

数据结构：并查集结构

朋友圈

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.util.*;
 
public class Main{
    public static class Node {
        public Set<Integer> friends = new HashSet<>();
    }
 
    public static HashMap<Node, Node> fatherMap;
    public static HashMap<Node, Integer> sizeMap;
 
    public static void main(String[] args) {
        //1、输入数据，组织数据结构
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n <= 0 || n >= 100000) {
            System.out.println(0);
            return;
        }
        Node[] nodes = new Node[n + 1];
        int tmp;
        fatherMap = new HashMap<Node, Node>();
        sizeMap = new HashMap<Node, Integer>();
        for (int i = 1; i <= n; ++i) {
            nodes[i] = new Node();
            fatherMap.put(nodes[i], nodes[i]);
            sizeMap.put(nodes[i], 1);
            while ((tmp = sc.nextInt()) != 0) {
                nodes[i].friends.add(tmp);
            }
        }
        //2、遍历每个节点，根据合并策略进行合并
        for (int i = 1; i < nodes.length; i++) {
            if (nodes[i].friends.size() == 0) continue;
            for (Iterator<Integer> iterator = nodes[i].friends.iterator(); iterator.hasNext(); ) {
                Integer one = iterator.next();
                if (!isSameSet(nodes[i], nodes[one])) {
                    union(nodes[i], nodes[one]);
                    n--;
                }
            }
        }
        //3、result
        System.out.println(n);
    }
 
    private static Node findHead(Node node) {
        Node father = fatherMap.get(node);
        if (father != node) {
            father = findHead(father);
        }
        fatherMap.put(node, father);
        return father;
    }
 
    public static boolean isSameSet(Node a, Node b) {
        return findHead(a) == findHead(b);
    }
 
    public static void union(Node a, Node b) {
        if (a == null || b == null) {
            return;
        }
        Node aHead = findHead(a);
        Node bHead = findHead(b);
        if (aHead != bHead) {
            int aSetSize = sizeMap.get(aHead);
            int bSetSize = sizeMap.get(bHead);
            if (aSetSize <= bSetSize) {
                fatherMap.put(aHead, bHead);
                sizeMap.put(bHead, aSetSize + bSetSize);
            } else {
                fatherMap.put(bHead, aHead);
                sizeMap.put(aHead, aSetSize + bSetSize);
            }
        }
    }
}

输出：

输出:2

题目三：01岛

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Islands{
	public static int countIslands(int[][] m) {
		if (m == null || m[0] == null) {
			return 0;
		}
		int N = m.length;
		int M = m[0].length;
		int res = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (m[i][j] == 1) {
					res++;
					infect(m, i, j, N, M);
				}
			}
		}
		return res;
	}
      //感染函数
	public static void infect(int[][] m, int i, int j, int N, int M) {
		if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {
			return;
		}
		m[i][j] = 2;
		infect(m, i + 1, j, N, M);
		infect(m, i - 1, j, N, M);
		infect(m, i, j + 1, N, M);
		infect(m, i, j - 1, N, M);
	}

	public static void main(String[] args) {
		int[][] m1 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
				        { 0, 1, 1, 1, 0, 1, 1, 1, 0 }, 
				        { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
				        { 0, 1, 1, 0, 0, 0, 0, 0, 0 }, 
				        { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, 
				        { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
				        { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
		System.out.println(countIslands(m1));
		int[][] m2 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
						{ 0, 1, 1, 1, 1, 1, 1, 1, 0 }, 
						{ 0, 1, 1, 1, 0, 0, 0, 1, 0 },
						{ 0, 1, 1, 0, 0, 0, 1, 1, 0 }, 
						{ 0, 0, 0, 0, 0, 1, 1, 0, 0 }, 
						{ 0, 0, 0, 0, 1, 1, 1, 0, 0 },
						{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
		System.out.println(countIslands(m2));
	}
}

输出：

1
2
3
1
> >