算法第一章 基础

算法第一章 基础

第一章 基础

基础编程模型

格式化输出

从标准输出流中打印随机生成的数值,“%.2f\n”表示输出两位小数精度的浮点型数值并换行。

cmd运行需要注意的几个地方:

  1. 我们的工程一般使用utf-8编码,但是windows系统默认gbk编码,所以编译javac会出现“找不到gbk编码的字符映射”。解决办法:编译时指定参数 -encoding utf-8

  2. “找不到某个类”,程序中引用了非当前目录的jar文件,在本路径编译会找不到jar包,需要执行参数:-Djava.ext.dirs=jar包作为路径

  3. “无法运行主类”,检查是否配置了classpath环境变量,CLASSPATH=".;%JAVA_HOME%\lib;%JAVA_HOME%\lib\tools.jar;"

  4. 如果被编译类有包,需要在该包下执行编译和运行,最终该类的编译和运行命令:

    javac -Djava.ext.dirs=D:\IdeaProjects\Algorithms\lib -encoding utf-8 chapter_1/programming_model/RandomSeq.java
    java -Djava.ext.dirs=D:\IdeaProjects\Algorithms\lib chapter_1/programming_model/RandomSeq 10 1 100

1
2
3
4
5
6
7
8
9
10
11
12
13
public class RandomSeq {
public static void main(String[] args) {
// 打印n个(lo,hi)之间的随机值
int N = Integer.parseInt(args[0]);
double lo = Double.parseDouble(args[1]);
double hi = Double.parseDouble(args[2]);
for (int i = 0; i < N; i++) {
// 返回随机实数
double x = StdRandom.uniform(lo, hi);
StdOut.printf("%.2f\n", x);
}
}
}

注意:java要求参数的数据类型和转换代码表示的数据类型必须相同,printf()的第一个String字符串也可以包含其他字符。所有非格式的字符串会被传递到输出之中,而格式化的字符串则会被参数的值所代替。例如:

1
Std.printf("PI is %.2f\n",Math.PI);

会打印出:PI is 3.14

标准输入

特点

标准输入流最重要的特点就是这些值会在程序读取之后消失,程序读取了就不能回退再次读取。

重定向与管道

使输出重定向到一个文件中,而不是终端打印:
java RandomSeq 1000 100.0 200.0 > data.txt,每次打印都会向文件追加内容。

从文件读取输入流而不是等待用户输入,“<”是一个操作符,它告诉系统从文件中作为输入流而不是等终端用户输入。
java Average < data.txt

将一个程序的输出重定向为一个程序的输入叫做管道
java RandomSeq 1000 100.0 200.0 | Java Average,该命令将RandomSeq的标准输出和Average的标准输入指定为了同一个流。看起来的效果就是Average运行时从RandomSeq的输出作为了自己的输入。这种写法的好处在于它能够突破输入输出流长度的限制,有效的利用了系统资源。RandomSeq调用了printf()时,向输入流末尾添加了一条字符串;Average调用readDouble()时,就从输入流开头删除了一个字符串。

二分查找

读取终端输入流中的值,如果该值在指定文件中不存在则返回这个值,否则不返回。

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
public class BinarySearch {
public static int rank(int key, int[] arr) {
// 使用lo和hi变量保证key一定在arr[lo...hi]中
int lo = 0;
int hi = arr.length - 1;
for (int i = 0; i < hi; i++) {
// 取中间值索引,当查找的范围在左边,lo始终为0,当查找的范围在右边,中间值索引就是起始值索引+前后折半的值
int mid = lo + (hi - lo) / 2;
// 小于中间值,查找范围缩小到左边
if (key < arr[i]) {
hi = mid - 1;
}
// 大于中间值,查找范围缩小到右边
if (key > arr[i]) {
lo = mid + 1;
} else {
return i;
}
}
return -1;
}

public static void main(String[] args) {
long start = System.currentTimeMillis();
// Reads all integers from a file and returns them as an array of integers. argument:filename
int[] whitelist = In.readInts(args[0]);
Arrays.sort(whitelist);
while (!StdIn.isEmpty()) {
// Reads the next token from standard input, parses it as an integer,
int key = StdIn.readInt();
if (rank(key, whitelist) < 0) {
StdOut.println(key);
}
}
long end = System.currentTimeMillis();
StdOut.println("time->:" + (end - start));
}
}

命令行参数:

编译忽略过期警告:
javac -Djava.ext.dirs=D:\IdeaProjects\Algorithms\lib -Xlint:deprecation  -encoding utf-8 
    chapter_1/programming_model/BinarySearch.java
运行:传入一个文件路径,等待用户输入,比较输入的值是否在文件中存在
java -Djava.ext.dirs=D:\IdeaProjects\Algorithms\lib  chapter_1/programming_model/BinarySearch 
    D:\IdeaProjects\Algorithms\algs4-data\tinyW.txt
运行:传入一个文件路径,指定输入流来源于文件,从tinyT.txt中作为输入流,比较tinyT.txt里的每个值是否在tinyW.txt中存在
java -Djava.ext.dirs=D:\IdeaProjects\Algorithms\lib  chapter_1/programming_model/BinarySearch 
    D:\IdeaProjects\Algorithms\algs4-data\tinyW.txt < D:\IdeaProjects\Algorithms\algs4-data\tinyT.txt

数据抽象

背包、队列和栈

背包(Bag)

是一种不支持从中删除元素的数据类型,其主要目的用来帮助用例(应用程序)收集元素并迭代遍历搜集到的所有元素(检查背包是否为空,或获取背包中元素的数量)。使用背包说明元素的处理是无序的。

典型用例:计算标准输入中所有double值的平均值和标准差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Stats {
public static void main(String[] args) {
Bag<Double> numbers = new Bag<Double>();
while (!StdIn.isEmpty()) {
numbers.add(StdIn.readDouble());
}
int N = numbers.size();
double sum = 0.0;
for (double x : numbers) {
sum += x;
}
double mean = sum / N;

sum = 0.0;
for (double x : numbers) {
sum += (x - mean) * (x - mean);
}
double std = Math.sqrt(sum / N - 1);

StdOut.printf("Mean: %.2f\n", mean);
StdOut.printf("Std dec: %.2f\n", std);
}
}

队列(Queue)

是一种基于先进先出(FIFO)策略的集合类型。队列是许多日常现象的模型,也是无数应用程序的核心。

典型用例:读取文件中的所有数字并放入数组中,使用队列和好处在于用例无需知道文件中的数字的大小即可将文件中的所有数字放入数组中,首先将文件中的所有数字按顺序放入队列中,再从队列中按顺序一个一个取出放入数组,队列中元素的顺序就是文件中数字的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class QueueDemo {
public static int[] readInts(String name) {
In in = new In(name);
Queue<Integer> q = new Queue<>();
while (!in.isEmpty()) {
q.enqueue(in.readInt());
}

int N = q.size();
int[] a = new int[N];
for (int i = 0; i < N; i++) {
a[i] = q.dequeue();
}
return a;
}

public static void main(String[] args) {
readInts(args[0]);
}
}

下压栈(栈、Stack)

是一种基于后进先出(LIFO)策略的集合类型。生活中常见的后进先出策略的例子比如:桌面上放成一叠的邮件,当收信时将邮件压入(push)最顶端,取信时从最顶端将其弹出(pop)。这种策略好处在于我们能够及时的看到最新的邮件,坏处就是当没有清理栈时,某些较早的邮件永远不会被阅读。

典型用例:用元素保存集合的同时颠倒他们的顺序,Reverse会把标准输入中的所有整数逆序排列。

1
2
3
4
5
6
7
8
9
10
11
12
public class Reverse {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
while (!StdIn.isEmpty()) {
stack.push(StdIn.readInt());
}

for (int i : stack) {
StdOut.println(i);
}
}
}

栈的典型用例:双栈算术表达式求值算法

编写一个算法来模拟系统运算算术表达式: ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) ,输入一个表达式字符串,为了简化问题,我们假设表达式只由运算符+、-、*、/,小括号,和数字组成,并且每个元素之间都用一个空格隔开。

双栈算术表达式求值算法核心利用了用两个栈:一个保存运算符、一个保存操作数。处理逻辑如下:

  • 当遇到操作数将操作数压入操作数栈
  • 当遇到运算符将运算符压入运算符栈
  • 忽略左括号
  • 当遇到右括号时,弹出一个运算符,弹出所需数量的操作数,并将操作数和运算符的运算结果压入操作数栈
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
public class Evaluate {
public static void main(String[] args) {
Stack<String> ops = new Stack<>();
Stack<Double> vals = new Stack<>();
while (!StdIn.isEmpty()) {
// 循环读取每一个操作符,如果是运算符则压入运算符栈
String s = StdIn.readString();
if (s.equals("(")) {
} else if (s.equals("+")) {
ops.push(s);
} else if (s.equals("-")) {
ops.push(s);
} else if (s.equals("*")) {
ops.push(s);
} else if (s.equals("/")) {
ops.push(s);
} else if (s.equals("sqrt")) {
ops.push(s);
} else if (s.equals(")")) {
// 如果运算符为 ) ,弹出运算符和操作数,计算结果并压入操作数栈
String op = ops.pop();
double v = vals.pop(); // 弹出栈顶的操作数。弹出栈元素是在栈中删除了的
if (op.equals("+")) {
v = vals.pop() + v; // 再弹出一个栈顶操作数,与前面弹出的栈顶操作数(v)做运算并重新赋值给变量v
} else if (op.equals("-")) {
v = vals.pop() - v; // 第二次弹出的操作数在前,第一次弹出的操作数在后。因为先进栈的操作数后弹出,后进栈的元素先弹出
} else if (op.equals("*")) {
v = vals.pop() * v;
} else if (op.equals("/")) {
v = vals.pop() / v;
} else if (op.equals("sqrt")) {
v = Math.sqrt(v);
}
vals.push(v); // 运算后的值入栈,进行运算的两个操作数被弹出(删除)了。
} else {
// 如果既不是运算符也不是括号,则就是数字,将其压入数值栈。
vals.push(Double.parseDouble(s));
}
}
StdOut.println(vals.pop());
}
}

求值算法轨迹图:
Alt text

集合类数据类型的实现

基于顺序存储结构的集合类型实现

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
public class ResizingArrayStack<Item> implements Iterable<Item> { 
private Item[] a;
private int N;

public ResizingArrayStack(int cap) {
a = (Item[]) new Object[cap];
}

public void push(Item item) {
if (N == a.length) {
resize(a.length * 2);
}
a[N++] = item;
}

public Item pop() {
Item item = a[--N];
a[N] = null;
if (N > 0 && N == a.length / 4) {
resize(a.length / 2);
}
return item;
}

public boolean isEmpty() {
return N == 0;
}

public int size() {
return N;
}

public void resize(int max) {
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < N; i++) {
temp[i] = a[i];
}
a = temp;
}

@Override
public Iterator<Item> iterator() {
return new ReverseArrayStack<>();
}

private class ReverseArrayStack<Item> implements Iterator<Item> {
private int i = N;

@Override
public boolean hasNext() {
return i == 0;
}

@Override
public Item next() {
return (Item) a[--i];
}
}
}

基于链式存储结构的集合类型实现

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
public class LinkedStack<Item> implements Iterable<Item> {
private Node first;
private int N;

private class Node<Item> {
private Item item;
private Node next;
}

private class listIterator<Item> implements Iterator<Item> {
private Node currentNode = first;

@Override
public boolean hasNext() {
return currentNode != null;
}

@Override
public Item next() {
Item item = (Item) currentNode.item;
currentNode = currentNode.next;
return item;
}
}

public void push(Item item) {
Node oldFirst = first;
first = new Node<>();
first.item = item;
first.next = oldFirst;
N++;
}

public Item pop() {
Node<Item> oldFirst = first;
first = first.next;
N--;
return oldFirst.item;
}

public boolean isEmpty() {
return first == null;
}

public int size() {
return N;
}

@Override
public Iterator<Item> iterator() {
return new listIterator<>();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LinkedQueue<Item> implements Iterable {
// ......
public void enqueue(Item item) {
Node<Item> oldLast = last;
last = new Node();
last.item = item;
if (isEmpty()) {
first = last;
} else {
oldLast.next = last;
}
N++;
}

public Item dequeue() {
Node<Item> oldFirst = first;
first = first.next;
if (isEmpty()) {
last = null;
}
N--;
return oldFirst.item;
}
}

更多拓展在练习题:

下压栈:

补全表达式转为中序表达式

中序表达式转后序表达式

后序表达式求值实现简单计算器

队列:

读取倒数第K个字符串

链表:

LinkedStackExercise.java

双向链式存储结构集合数据类型实现:

Ex31_DoubleLinkedStack.java

随机背包:

Ex34_RandomBag.java

Josephus生存游戏:

Ex37_Josephus.java

可连接队列、栈:

Ex47.java

算法分析

案例研究:并查集(union-find)算法

问题由来 —— 动态连通性

问题:

程序从输入中每次读取一对整数 P 和 Q ,如果已知的所有整数对不能证明他们是“相连”的,那么把他们“连起来”,并打印;如果能证明他们是相连的则不处理,继续读取下一对整数对。当两个对象(整数点)相连时称为属于一个等价类

概念:

如果两个对象“相连”是一种等价关系,那么它具有以下特性:

  • 自反性:P和P是相连的(就是一个点和自己本身是相连的,em…);
  • 对称性:若P和Q是相连的,那么Q和P也是相连的;
  • 传递性:若P和Q相连且Q和R相连,那么P和R是相连的

理解并查集

以上问题其实就是并查集的一个具体案例,关于并查集,解释如下:

并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。

“并查集”是一种不相交集合的数据类型,初始时并查集中的元素是不相交的,经过一系列的基本操作(Union),最终合并成一个大的集合。

API

  • 初始化触点
  • 连接触点
  • 某个触点所在的连通分量
  • 判断两个触点是否在同一个连通分量之中
  • 返回连通分量的数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public interface UF {
/**
* 连接P和Q
*/
void union(int p, int q);

/**
* p所在分量(相等整数对)的标识符
*/
int find(int p);

/**
* p和q存在同一分量返回true
*/
boolean connected(int p, int q);

/**
* 分量的个数
*/
int count();
}

实现一:quick-find 算法

数据结构:数组

  1. 用数组 id[] 表示每一个触点的值,数组索引表示触点,触点的值就是分量的值,触点值相同表明分量相同。
  2. 初始化时每个触点的值都是该触点的索引。

    • 比如:触点0 = id[0] = 0; 触点1 = id[1] = 1; 触点3 = id[3] = 3;
  3. 多个触点属于同一个连通分量时,其中某个触点的值“代表”该连通分量的值,把其他触点的值统一成所属分量的代表值,比如:

    • 要把id[4] (值为4)id[8] (值为8) 相连为同一分量,可以把id[4]的值改成id[8]的值,那么把 id[8] 值称为该连通分量的代表(或标识符或值);也可以把id[8]的值改成id[4]的值,连通分量的值就是id[4]了。

    • 要把id[5] (值为5)id[4] (假设所属分量值为8) 相连为同一分量,连通分量的值以id[5]为代表,那么所有值为 8 的分量的值都改成了 5。

  4. 连通分量中的所有触点的值是统一的。

算法分析

可以快速进行 find 操作,即可以快速判断两个节点是否连通。

同一连通分量的所有节点的 id 值相等。

但是 union 操作代价却很高,需要将其中一个连通分量中的所有节点 id 值都修改为另一个节点的 id 值。

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
public class QuickFind implements UF {
private int[] id; // 连通分量标识符集合
private int count; // 连通分量数量

/**
* 初始化所有连通分量
*/
QuickFind(int N) {
count = N;
id = new int[N];
for (int i = 0; i < count; i++) {
id[i] = i;
}
}

@Override
public void union(int p, int q) {
int pID = find(p);
int qID = find(q);

if (pID == qID) {
// 已经在同一个分量中不做处理
return;
}

for (int i = 0; i < count; i++) {
if (id[i] == pID) {
id[i] = qID;
}
count--;
}
}

@Override
public int find(int p) {
return id[p];
}

@Override
public boolean connected(int p, int q) {
return id[p] == id[q];
}

@Override
public int count() {
return count;
}
}

实现二:quick-union 算法

数据结构:树

  1. 同样以 id[] 表示每一个节点(触点)的值,但节点的值不是分量的值,每一个节点值是以其父节点的索引号的id[]值,该节点最终的值是根节点的值(父节点指向父节点,直到指向根节点)。

    • 比如节点4(id[4]=9)节点8 的父节点,那么节点8id[8]的值就是id[4],即:id[8] = id[4] = 9
  2. 初始化时每个触点的值都是该触点的索引,并且都是根节点。

  3. 属于同一个连通分量的所有节点都属于同一颗数,判断是否属于同一分量需要判断是否属于同一棵树,我们可以把根节点代表分量的标识符。

  4. 两个节点的联合操作,操作的是两个节点的根节点,只需要将一个根节点的父节点设为另外一个根节点,这样两个节点(分量)联合成了一个节点(分量)。

    • 比如:初始化时,每个节点都是根节点。 id[0] = 0; id[1] = 1; id[3] = 3; id[7] = 7 …
    • 联合节点 0 和 1,将id[0]的父节点设为id[1],即:id[0] = id[1] = 1
    • 联合节点 3 和 0,将id[3]的父节点设为id[0],即:id[3] = id[0] = id[1] = 1
    • 联合节点 1 和 7,将id[1]的父节点设为id[7],即:id[1] = id [7] = 7(此时id[3] = id[0] = id[1] = id [7] = 7)

算法分析

可以快速进行 union 操作,只需要修改一个节点的 id 值即可。

union操作,固定的将左边的树链接到右边的树,导致树的深度很深,进行find()操作时效率变低。

但是 find 操作开销很大,因为同一个连通分量的节点 id 值不同,id 值只是用来指向另一个节点。因此需要一直向上查找操作,直到找到最上层的节点。

这种方法可以快速进行 union 操作,但是 find 操作和树高成正比,最坏的情况下树的高度为触点的数目。

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
public class QuickUnion implements UF {
private int[] id; // 树的每一个节点(触点)
private int count; // 连通分量(根节点)的数量

QuickUnion(int N) {
count = N;
id = new int[N];
for (int i = 0; i < count; i++) {
id[i] = i;
}
}

@Override
public void union(int p, int q) {
// 获取两个节点所属分量(根节点)
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
// 把p的根节点的爸爸设为q的根节点,这样p和q就有了共同的爸爸。
id[pRoot] = qRoot;
count--;
}

@Override
public int find(int p) {
// 当id[p]的值是本身,说明它是根节点(分量名);若不是,向上循环找到根节点。
while (p != id[p]) {
p = id[p];
}
return p; // 所在分量就是根节点
}

@Override
public boolean connected(int p, int q) {
return id[p] == id[q];
}

@Override
public int count() {
return count;
}
}

轨迹图:

Alt text

实现三:加权 quick-union 算法

算法分析

加权 quick-union 算法的出现是为了解决 quick-union 中find()操作随着树的深度加深成本变得越来越昂贵的问题。

不再固定的将左边的树链接到右边的树,而是根据树的深度(节点的个数)决定将深度小的树链接在深度大的树,由此降低find()操作次数。

数据结构

  1. 和 quick-union 结构相同,仅仅添加了一个用于记录每个分量个数的数组

  2. 不再是把p的根节点的爸爸设为q的根节点了,而是比较p的分量个数和q的分量个数,分量个数小的认分量个数大的当爸爸

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
public class WeightQuickUnion implements UF {
private int[] id; // 每个触点的值是父链接
private int count; // 连通分量个数
private int[] sz; // 各个根节点对应的分量大小(节点个数)

WeightQuickUnion(int N) {
count = N;
id = new int[N];
for (int i = 0; i < count; i++) {
id[i] = i;
}
// 初始化每个根节点对应分量的大小都是1
sz = new int[N];
for (int i = 0; i < count; i++) {
sz[i] = 1;
}
}

@Override
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
// 不再是把p的根节点的爸爸设为q的根节点了,而是比较p的分量个数和q的分量个数,分量个数小的认分量个数大的当爸爸
if (sz[pRoot] > sz[qRoot]) {
id[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
} else {
// 当p分量大小 <= q分量大小时,默认q的根节点认q的根节点当爸爸
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
count--;
}

@Override
public int find(int p) {
while (p != id[p]) {
p = id[p];
}
return p;
}

@Override
public boolean connected(int p, int q) {
return find(p) == find(q);
}

@Override
public int count() {
return count;
}
}

轨迹图:

Alt text

实现四:路径压缩的加权 quick-union 算法

算法分析

路径压缩的加权 quick-union 算法是为了优化find()操作,减少查找父节点的次数,从而提升查找的效率;

使用路径压缩的加权 quick-union 算法是解决动态连通性问题的最优解;

它将每一个子节点都挂在根节点形成一个近似扁平的树状结构;

每次查找指定节点的根元素(分量)时,都将路径上(该节点的所有父节点)遇到所有节点挂在根节点之下;

压缩加权后的算法find()效率与 quick-find 的效率非常接近。

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
public class WeightQuickUnion implements UF {
public int pathCompressionFind(int p) {
// 先向上循环找到根节点
int root = p;
while (root != id[root]) {
root = id[root];
}
// 再次循环,如果当前节点不是根节点,把当前节点挂在根节点上成为根节点的一级节点。
while (p != id[p]) {
int tem = p;
p = id[p];
id[tem] = root;
}
return root;
}

public void union(int p, int q) {
int pRoot = pathCompressionFind(p);
int qRoot = pathCompressionFind(q);
if (pRoot == qRoot) {
return;
}
// 不再是把p的根节点的爸爸设为q的根节点了,而是比较p的分量个数和q的分量个数,分量个数小的认分量个数大的当爸爸
if (sz[pRoot] > sz[qRoot]) {
id[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
} else {
// 当p分量大小 <= q分量大小时,默认q的根节点认q的根节点当爸爸
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
count--;
}
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×