学步园

数据结构与<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>实验题 11.3 培养箱分配问题<br /> ★ 问题描述 :<br /> 生物学家 Finder 最近发现了一种有趣的虫子 BUG ， BUG 有两种性别，当 相<br /> 同性别 的 BUG 生活在一起时，会发生剧烈的打斗，而当不同性别的 BUG 在一<br /> 起时，则 会 相处的非常好。<br /> 现在， Finder 找到了很多 BUG 虫，并将它们命名为 1 系列、 2 系列、 3 系<br /> 列 …… N 系列，每个系列的 BUG 虫之间是同性别的。 Finder 要将它们分配到培<br /> 养箱里培养，每个箱里两只。为了防止同性别之间的打斗，要求每个箱子里的<br /> BUG 虫是不同性 别 的。<br /> ★ 实验任务：<br /> 现在 Finder 拟定了一个分配方案，但由于培养箱数量太多， Finder 也不能 确<br /> 定这种分配方案是否可行，即同一个培养箱中的 BUG 虫 会 不会打斗。现在， Fi nder<br /> 找到你，要你写一个程序验证他的分配方案是否可行。<br /> ★ 数据输入：<br /> 由 input.txt 给出输入。第一行有两个数 N ， M ，表示 Finder 有 N 个系列的 BUG<br /> 虫，编号为 1 到 N ， M 表示有 M 个培养箱，接下来 M 行每行两个数 A,B ，表 示<br /> 将 A 系列的 BUG 虫和 B 系列的 BUG 虫 放在 一起培养 (1<=A<=N,1<=B<=N) 。 注<br /> 意，输入数据有多组，必须处理到文件末尾。<br /> ★ 结果输出 :<br /> 输出到 ouput.txt 文件。每个方案输出一行，如果方案可行，输出 YES ， 否<br /> 则输出 NO 。<br /> ★ 提示 :<br /> 多组数据 处理到文件末尾 的伪代码如下：<br /> 输入示例<br /> input.txt<br /> 3 3<br /> 2 1<br /> 2 3<br /> 3 1<br /> 输出示例<br /> output.txt<br /> NO

本题可以使用路径压缩来加快速度，但是由于调试原因，所以没有加入。

不过要过ZOJ应该还是要使用路径压缩和 union小树到大树的。

我的思想是

例如这样一组数据

6 8
1 2
3 4
5 6
1 4
3 6
4 5
1 3

1 6
当出现1 2时候

我们把1和2各自归为一个集合，并且这两个集合是相对的。

当3 4时，因为还都是独立的元素，所以再各自归为一个集合，并且这两个集合是相对的。

当5 6时，因为还都是独立的元素，所以再各自归为一个集合，并且这两个集合是相对的。

当出现1 4时 因为 1 和4 都已经是集合的元素了，所以我们把那两个相对的集合合并。

也就是变成了(1 3)-(2 4)

当出现3 6时，因为 3 和6 都已经是集合的元素了，所以我们把那两个相对的集合合并。

也就是变成了(1 3 5  )-(2 4 6)

当出现4 5的时候，因为是出现在相对集合里面，所以不进行操作。

当出现1 3的时候，由于出现在同一个集合里面，所以不符合要求！可以输出no

#include <stdio.h></p> <p>int Find(int n, bool root[], int Set[])<br /> {<br /> int i;<br /> i = n;<br /> while(1)<br /> {<br /> if (root[i] == true)<br /> return i;<br /> i = Set[i];<br /> }<br /> }</p> <p>int main()<br /> {<br /> int m,n;<br /> int a,b;<br /> int flag;<br /> int i;<br /> int RootA,RootB;<br /> int Set[3000];<br /> bool root[3000];<br /> while (scanf("%d%d", &n, &m)!=EOF)<br /> {<br /> for(i=0;i<=n;i++)<br /> {<br /> Set[i] = i;<br /> root[i] = true;<br /> }<br /> flag = 0;<br /> for (i=0;i<m;i++)<br /> {<br /> scanf("%d%d", &a, &b);<br /> if (flag) continue;<br /> RootA = Find(a ,root, Set);<br /> RootB = Find(b,root, Set);<br /> if (RootA == RootB)<br /> flag = 1;<br /> else<br /> {<br /> if (Set[RootA]==RootA&&Set[RootB]==RootB)<br /> {<br /> root[RootA] = true;<br /> root[RootB] = true;<br /> Set[RootA] = RootB;<br /> Set[RootB] = RootA;<br /> }<br /> else if (Set[RootA]==RootA&&Set[RootB]!=RootB)<br /> {<br /> root[RootA] = false;<br /> root[RootB] = true;<br /> Set[RootA] = Set[RootB];<br /> } else if (Set[RootB]==RootB&&Set[RootA]!=RootA)<br /> {<br /> root[RootB] = false;<br /> root[RootA] = true;<br /> Set[RootB] = Set[RootA];<br /> } else if (Set[RootB]!=RootB&&Set[RootA]!=RootA)<br /> {<br /> root[RootA] = false;<br /> root[Set[RootA]] = false;<br /> root[RootB] = true;<br /> root[Set[RootB]] = true;<br /> //已经在两个相对集合里面了，就不要再改变了<br /> if (Set[RootA] != RootB)<br /> {<br /> Set[Set[RootA]] = RootB;<br /> Set[RootA] = Set[RootB];<br /> }<br /> }<br /> }<br /> }<br /> if (flag)<br /> printf("NO/n");<br /> else<br /> printf("YES/n");<br /> }<br /> return 0;<br /> }<br />