并差集

1并差集某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？Input测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N(1000)和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。注意:两个城市之间可以有多条道路相通,也就是说33121221这种输入也是合法的当N为0时，输入结束，该用例不被处理。4畅通工程2/2Output对每个测试用例，在1行里输出最少还需要建设的道路数目。SampleInput4213433312132352123599900SampleOutput102998HintHintHugeinput,scanfisrecommended.Source浙大计算机研究生复试上机考试-2005年5转化现实问题计算机问题数学问题6现实到数学思考？？有一组不相交的集合SMAKE_SET：构造新集合，指定代表。UNION(X,Y):合并集合Ｘ和集合Ｙ。指定代表FIND(x):返回包含x的集合的代表7数学到计算机（1/2）不相交的数据结构保持一组不向交的动态集合S={S1，S2,…,Sk}.每个集合通过一个代表来识别，代表即集合中的某个成员。寻找某集合两次，两次之间不修改集合，那么两次得到的答案应该是相同的选择代表可以任意，应该让问题尽可能简化，但是每个集合的代表必须唯一性质：2318数学到计算机（1/2）操作：MAKE_SET(x):建立一个新的集合，其唯一成员（因而其代表）就是x。因为各集合是不相交的，故要求x没有在其它集合出现过。FIND_SET(x):返回一个指针，指向包含x的（唯一）集合的代表。12UNION(X,Y):将包含x和y的动态集合（比如说Sx和Sy）合并为一个新的集合（即这两个集合的并集。合并后，要选择新代表。39哈哈哈快晕了吧？？？来个例子尝尝10例子（1/2）S={S1，S2}；S1={1，2，3，4，5，6}标示为7的集合S2123456标示为1（find()返回1）的集合S1S={S1，S2}；S2={7，8，9}78911例子(2/2）合并（union()）123475689简单吧12具体实现如何存储数据集合？MAKE_SET(x)如何实现合并操作？UNION(X,Y)结果在哪里保存着啊？PARENT[X]四个问题如何实现查找操作？FIND(x)13存储大部分数据结构都可以用两种方式存储：链式存储结构和顺序存储结构。链式存储：容易想到，直观，容易合并（不讲）。顺序存储：更为简单，采用有根树表示（非常好）。14步骤定义一个一维数组，可以保存两种信息查找某数据是瞬时的，太牛了。寻找它的代表合并两个集合15优化：按秩合并（1/2）看着挺恐怖的。实际很简单。就是元素个数少的集合加入到元素个数多的集合中去。16优化：路径压缩(难点)(2/2)数据直接连系代表1234栈：1432最终结果：x=4，parent[x]=3,返回值parent[x]x=1，parent[x]=1,返回值parent[x]。递归结束，返回parent[x]=1x=2，parent[x]=1,返回值parent[x]x=3，parent[x]=2,返回值parent[x]find(x){If(x!=parent[x])//x==parent[x]表示x为树根parent[x]=find(parent[x]);returnparent[x];}17代码一（1/2)#definemax_size元素个数intparent[max_size];//用memset(parent,-1,sizeof(parent));初始化intfind(intx){if(parent[x]0)parent[x]=find(parent[x]);returnparent[x]0?parent[x]:x;}voidunion_set(intx,inty){x=find(x),y=find(y);if(x!=y){if(parent[x]parent[y]){parent[x]+=parent[y];parent[y]=x;}else{parent[y]+=parent[x];parent[x]=y;}}}这种实现用集合中元素个数的相反数来标示树根18代码二(2/2)#definemax_size元素个数intparent[max_size],rank[max_size];voidmake_set(){inti;for(i=0;imax_sizw;i++){parent[i]=i;rank[i]=1;}}intfind(intx){if(x!=parent[x])parent[x]=find(parent[x]);returnparent[x];}voidunion_set(intx,inty){x=find(x),y=find(y);if(x!=y){if(rank[x]rank[y]){parent[x]=y;rank[y]+=rank[x];}else{parent[y]=x;rank[x]+=rank[y];}}}这种实现用parent[i]=i标示树根19习题简单：1856moreisbetter1213HowManyTables1232畅通工程不简单：1829ABug'sLife都是在杭电上哟！20