来自于《算法：C 语言实现》
1.
1 // 快速查找算法
2
3 #include <stdio.h>
4 #define N 10000
5
6 int main()
7 {
8 int i, p, q, t, id[N];
9 for (i = 0; i < N; ++i)
10 {
11 id[i] = i;
12 }
13 while (scanf("%d %d", &p, &q) == 2)
14 {
15 if (id[p] == id[q])
16 {
17 continue;
18 }
19 for (t = id[p], i = 0; i < N; ++i)
20 {
21 if (id[i] == t)
22 {
23 id[i] = id[q];
24 }
25 }
26 printf(" %d %d\n", p, q);
27 }
28 }
2.
1 // 快速合并算法
2
3 #include <stdio.h>
4 #define N 10000
5
6 int main()
7 {
8 int i, j, p, q, id[N];
9 for (i = 0; i < N; ++i)
10 {
11 id[i] = i;
12 }
13 while (scanf("%d %d", &p, &q) == 2)
14 {
15 for (i = p; i != id[i]; i = id[i]);
16 for (j = q; j != id[j]; j = id[j]);
17 if (i == j)
18 {
19 continue;
20 }
21 id[i] = j;
22 printf(" %d %d\n", p, q);
23 }
24 }
3.
1 // 加权快速合并算法
2
3 #include <stdio.h>
4 #define N 10000
5
6 int main()
7 {
8 int i, j, p, q, id[N], sz[N];
9 for (i = 0; i < N; ++i)
10 {
11 id[i] = i;
12 sz[i] = 1;
13 }
14 while (scanf("%d %d", &p, &q) == 2)
15 {
16 for (i = p; i != id[i]; i = id[i]);
17 for (j = q; j != id[j]; j = id[j]);
18 if (i == j)
19 {
20 continue;
21 }
22 if (sz[i] < sz[j])
23 {
24 id[i] = j;
25 sz[j] += sz[i];
26 }
27 else
28 {
29 id[j] = i;
30 sz[i] += sz[j];
31 }
32 printf(" %d %d\n", p, q);
33 }
34 }
4.
1 // 带有等分路径压缩的加权快速-合并算法
2
3 #include <stdio.h>
4 #define N 10000
5
6 int main()
7 {
8 int i, j, p, q, id[N], sz[N];
9 for (i = 0; i < N; ++i)
10 {
11 id[i] = i;
12 sz[i] = 1;
13 }
14 while (scanf("%d %d", &p, &q) == 2)
15 {
16 for (i = p; i != id[i]; i = id[i])
17 {
18 id[i] = id[id[i]];
19 }
20 for (j = q; j != id[j]; j = id[j])
21 {
22 id[j] = id[id[j]];
23 }
24 if (i == j)
25 {
26 continue;
27 }
28 if (sz[i] < sz[j])
29 {
30 id[i] = j;
31 sz[j] += sz[i];
32 }
33 else
34 {
35 id[j] = i;
36 sz[i] += sz[j];
37 }
38 printf(" %d %d\n", p, q);
39 }
40 }
posted on 2011-04-20 17:01
unixfy 阅读(373)
评论(0) 编辑 收藏 引用