//从今天起准备认真看完这本书。本渣虽然笨，但是窝懒啊。。。。
//今天开始看第一章。希望坚持下去。
第一章 引言
通过讨论连通问题的几种算法，来引出算法的重要性。
1.1 连通问题的快速查找算法
感觉就是把每个点染色，每个颜色代表一堆，互相连通。每次输入两个点，把两个点所属那个颜色改为相同，这样他们代表就都互相连通。
时间复杂度：O(MN), M是输入指令次数，N是点个数
//1.1 连通问题的快速查找算法
#include <stdio.h>
#define N 10
int id[N]; // 表示每个点的色
int main()
{
//freopen("in.txt", "r", stdin);
int i, t, p, q;
for (i = 0; i < N; ++i)
id[i] = i; // 开始每两个点都不连通，所以每个点一个颜色
while (scanf("%d%d", &p, &q) == 2) {
if (id[p] != id[q]) {
for (t = id[p], i = 0; i < N; ++i)
if (id[i] == t) // 把所有和p一个颜色的点染成q的颜色
id[i] = id[q];
}
for (i = 0; i < N; ++i)
printf("%d ", id[i]);
printf("
");
}
return 0;
}
1.2 连通问题的快速合并解法
就是两个点相同就把两个点放到同一棵树上，这样两个点根相同代表他们连通。每次找到两个点的根，如果不相同，就把一个跟连到另一个根上。
时间复杂度：Ｏ（ＭＮ），M是输入指令次数，N是点个数。当Ｍ＞Ｎ时，执行次数为ＭＮ／２
//1.２ 连通问题的快速合并算法
#include <stdio.h>
#define N 10
int main()
{
//freopen("in.txt", "r", stdin);
int i, j, p, q;
int id[N]; // 表示每个点的父节点
for (i = 0; i < N; ++i)
id[i] = i; // 开始每两个点都不连通，所以每个点的父节点是自己
while (scanf("%d%d", &p, &q) == 2) {
for (i = p; i != id[i]; i = id[i])
/*nothing*/ ; // 当该节点的父节点与该节点相等时，证明该节点是根
for (j = q; j != id[j]; j = id[j])
/*nothing*/ ;
if (i != j) //此时i为p的根，j为q的根
id[i] = j;
for (i = 0; i < N; ++i)
printf("%d ", id[i]);
printf("
");
}
return 0;
}
１.３ 加权快速合并算法
记录每棵树的节点个数，把节点少的根连到节点多的根。
时间复杂度：lgN。每次找一个节点的根只需要lgN，因为1+lgi=lg2+lgi=lg(2i)=lg(i+i)<=lg(i+j)
//1.3 加权快速合并算法
#include <stdio.h>
#define N 10
int main()
{
freopen("in.txt", "r", stdin);
int i, j, p, q;
int id[N]; // 表示每个点的父节点
int sz[N]; // 每棵树的节点个数
for (i = 0; i < N; ++i) {
id[i] = i; // 开始每两个点都不连通，所以每个点的父节点是自己
sz[i] = 1; // 开始每个节点一棵树
}
while (scanf("%d%d", &p, &q) == 2) {
for (i = p; i != id[i]; i = id[i])
/*nothing*/ ; // 当该节点的父节点与该节点相等时，证明该节点是根
for (j = q; j != id[j]; j = id[j])
/*nothing*/ ; //此时i为p的根，j为q的根
if (i != j && sz[i] < sz[j]) {
//当j所在树节点多，就把i连j上
id[i] = j;
sz[j] += sz[i];
} else if (i != j) {
id[j] = i;
sz[i] += sz[j];
}
for (i = 0; i < N; ++i)
printf("%d ", id[i]);
printf("
");
}
return 0;
}
1.4 等分路径压缩
在查找根的过程中，使沿路每个节点的ｉｄ指向根。
时间复杂度：接近Ｏ（ｎ）？
//1.4 等分路径压缩
#include <stdio.h>
#define N 10
int main()
{
//freopen("in.txt", "r", stdin);
int i, j, p, q;
int id[N]; // 表示每个点的父节点
int sz[N]; // 每棵树的节点个数
for (i = 0; i < N; ++i) {
id[i] = i; // 开始每两个点都不连通，所以每个点的父节点是自己
sz[i] = 1; // 开始每个节点一棵树
}
while (scanf("%d%d", &p, &q) == 2) {
for (i = p; i != id[i]; i = id[i]) {
//printf("id[%d]=%d, id[id[%d]]=%d
", i, id[i], i, id[id[i]]);
id[i] = id[id[i]]; // --------①--------
}
for (j = q; j != id[j]; j = id[j])
id[j] = id[id[j]];
if (i != j && sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
} else if (i != j) {
id[j] = i;
sz[i] += sz[j];
}
for (i = 0; i < N; ++i)
printf("%d ", id[i]);
printf("
");
}
return 0;
}
说一下窝对①处的理解。
如果该节点为根节点或深度为2，即
或
则不改变。
如果深度为3，则
->
深度为4
->
深度为5
深度为6
这样每个节点的深度小了。搜索根节点的复杂度变小。（然而我觉得并没有什么卵用。。。。）