并查集[讲义]

1、并查集初步及应用,引例：犯罪团伙 1、最小生成树 2、细胞个数 3、房间问题(noi94) 4、代码等式 5、银河英雄传说(noi2002),并查集的概念及运算,内容：,引例：【犯罪团伙】 警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。 请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从1至n。 输入： 第一行：n（=10000,罪犯数量）， 第二行：m（=100000，关系数量） 以下若干行：每行两个数：I 和j，中间一

2、个空格隔开，表示罪犯i和罪犯j相互认识。 输出：一个整数，犯罪团伙的数量。,输入： 11 8 1 2 4 5 3 4 1 3 5 6 7 10 5 10 8 9,输出： 3,测试数据说明： 1 s 共10个测试数据： （1）5个数据： n=n=9000, 100000=m=90000;,建立无向图的模型。 如果x和y认识，结点x和y建立一条无向边。 求无向图的连通分量（dfs;bfs） 时间和空间！ 邻接矩阵：空间太大，超时。 邻接表：空间满足，时间查过1s,最容易想到的算法：,抽象的算法：,开始把n个人看成n个独立集合。 每读入两个有联系的人i和j，查找i和j所在的集合p和q，如果p和q是同

3、一个集合，不作处理；如果p和q属于不同的集合，则合并p和q为一个集合。 最后统计集合的个数即可得到问题的解。,需要将n个不同的元素划分成一组不相交的集合。开始时，每个元素自己成一个单元素集合，然后按照一定的顺序或问题给定的条件和要求将属于同一组元素（有特定关系）所在的集合合并，最后统计集合的个数往往就是问题的解。 在这个过程中要反复的用到查询某个元素属于哪个集合的运算；两个不同集合合并的运算。适合描述这类问题的抽象数据结构类型称为并查集（合并与查找）。,一类问题模型：,并查集是一种树型的数据结构，用于处理一些不相交集合S=S1, S2, ,Sn, 每个集合Si都有一个特殊元素rootSi,称为

4、集合的代表元.,并查集支持三种操作： Init（X）: 集合初始化：把元素xi加到集合Si中。每个集合Si只有一个独立的元素xi,并且元素xi就是集合Si的代表元素。 Find(x): 查找：查找xi所在集合Si的代表rootSi。 优化：路径压缩。 Union(x, y): 合并：把x和y所在的两个不同集合合并。,并查集的一个重要的应用是确定给定集合上的等价关系的个数。 等价关系是一个具有自反、对称和传递三个性质的关系。 等号“=”在实数集合R上是一个等价关系。 对于实数中的任意x、y、z。一定满足下列关系： 1）、x=x （自反性） 2）、如果x=y，则y=x （对称性） 3）、如果x=y

5、，y=z，则x=z （传递性）,【犯罪团伙】问题：,“同一团伙“抽象成无向图的”连通” ”连通”可以看成n个人的集合上的一个等价关系。 对于图中的任意3个顶点：A,B,C。有： 1）、A连通A .（自反性） 2）、如果A连通B，则B连通A .（对称性） 3）、如果A连通B，B连通C，则A连通C .（传递性） 一个连通分量就是一个等价关系（连通），等价关系的个数就是连通分量的个数。 一个等价关系对应一个集合。 一个集团对应一个集合。,并查集的树型结构实现,采用树型结构实现并查集的基本思想是： 每个子集合用一棵树来表示。树中的每个结点用于存放集合中的一个元素。 树中的每个结点x设置一个指向父亲的指

6、针。 fatherx 用根结点的元素代表该树所表示的集合。,Init（X）: 集合初始化： fatherxi=0(或者xi); 每个结点都是一颗独立的树， 是该树的代表元素。,三种操作：,Find(x): 查找： 查找x所在集合Si的代表rootSi。 即：查找x所在树的树根结点（代表元素）。 顺着x往上找，直到找到根节点，也就确定了x所在的集合。,Union(x, y): 合并x和y所在的不同集合。 p=find(x) ；q=find(y); if pq then fatherp=q 或 fatherq=p,3,11,6,输入： 11 8 1 2 4 5 3 4 1 3 5 6 7 10 5

7、 10 8 9,11,初始化:,合并:,树根（集合代表元素）： Father1=0; father8=0; father11=0 孩子结点： father2=1; father4=3; father5=4; father9=8,查找： find(5)=1 find(7)=1 find(9)=8 find(11)=11 find(1)=1 find(8)=8,合并：union（x，y） union（5，9） p=find(5)=1; q=find(9)=8; fatherq=p; 或 fatherp=q father8=1; father1=8,算法的 实现：, ai：为结点i的父亲指针。 初始

8、值为0，表示是树根。每个结点看成一颗树。 每读入两个结点x，y，找x的树根p，令p=find(x);找y的树根q，令q=find(y);如果p=q，不做处理；如果属于不同的两棵树即：pq，则合并两棵树. 具体操作是： 把p看作q的孩子或者把q看作p的孩子: ap=q或者aq=p 最后统计树的数量，即ai=0的结点的数量,即问题的解：犯罪集团的个数。,【犯罪团伙】问题：,输入： 11 8 1 2 4 5 3 4 1 3 5 6 7 10 5 10 8 9,const max=10000; var a:array1.maxof longint; /父亲指针 i,j,m,n,ans,x,y,p,q:

9、longint; function find(i:longint):longint;非递归算法找i的根 var j,k,t:longint; begin j:=i;/顺着结点i开始向上找，直到根为止。 while aj0 do j:=aj; find:=j; end; begin,程序算法：,readln(n);/读入顶点数 readln(m);/读入关系：边 fillchar(a,sizeof(a),0);默认根标志是0，开始全是树根 for i:=1 to m do begin readln(x,y); p:=find(x); 查找x的根 q:=find(y); 查找y的根 if pq t

10、hen aq:=p; 合并p和q子树 end; ans:=0;树根记数 for i:=1 to n do if ai=0 then inc(ans);记录树根结点 writeln(ans); end.,function find(i:longint):longint; /递归算法找i的根 var j,k,t:longint; begin if ai=0 then exit(i); /若i为根，返回本身结点序号 find:=find(ai); /否则继续向上找 end;,Find(i)递归算法,改进运行时间的两种启发式策略：,1、按秩合并 秩=树的高度 高度小的树的根指高度向大树的根。减少整个树

11、的高度，提高查找效率。 2、路径压缩 根据等价关系的传递性，该变树的结构，使树变得扁平，从而提高查找效率。,Union（2，1） Union（3，2） Union（3，4） Union（n，n-1） Find(1) Find(2) Find(n),按秩合并,N次查找总代价=n*(n+1)/2= (n2),O(nlgn),按秩合并,路径压缩:查找find(i)时进行,路径压缩实际上是在找完根结点之后，在回来的时候顺便把路径上元素的父亲指针都指向根结点这样可以减小以后的查找次数 实现路径压缩的简单非递归算法：从结点到根走两遍：第一遍找根；第二遍是将路径上的所有结点的父亲都设为根。,Union(5,

12、10),树越扁平查找效率越高。,路径压缩程序： 非递归算法： function find(i:longint):longint;非递归算法找i的根 var j,k,t:longint; begin j:=i; while aj0 do j:=aj; / 顺着i向上找根。 find:=j; k:=i; 从i开始对子树结点进行路径压缩 while ak0 do begin t:=k;k:=ak;at:=j;end; end;,function find(i:longint):longint; 采用递归算法：寻找结点i的树根，并对结点i所在的子树进行路径压缩，返回调整后的i的父指针（根） begin

13、 if ai=0 then exit(i); 若i为根，返回本身结点序号 find:=find(ai);递归找根结点 ai:=find; 路径压缩：找到根后，按原路返回的同时，进行中间结点的逆序路径压缩，一次性完成 end;,递归算法（多采用此法）：,if aai=0 then exit(ai); 若i的父结点为根，则返回父结点,const max=10000; var a:array1.maxof longint; i,j,m,n,sum,x,y,p,q:longint; function find(i:longint):longint; begin if ai=0 then exit(I)

14、; if aai=0 then exit(ai); find:=find(ai); ai:=find; end; procedure main; begin fillchar(a,sizeof(a),0); readln(n); readln(m); for i:=1 to m do begin readln(x,y); p:=find(x); q:=find(y); if pq then aq:=p; end;,sum:=0; for i:=1 to n do if ai=0 then inc(sum end; procedure print; begin writeln(sum); end

15、; BEGIN main; print; END.,完整程序,并查集的时间复杂度,其中(n)是Ackermann函数的某个反函数，增长速度及其缓慢。 (n)=4。所以并查集的单次查找操作的时间复杂度也几乎是常数级的。,按秩合并：时间：O(m*lg(n) 路径压缩：最坏:O(n+lg(n)） 按秩合并和路径压缩： O(m(n) 经过启发式合并和路径压缩之后的并查集，执行m次查找的复杂度为O(m(n)；算法导论p312 （犯罪集团：m=100000）,n个元素的m次不相交集合操作,例1 最小生成树,用并查集实现kruskal算法,算法步骤： 1、把图中的边按权值从小到大排序。 2、按从小到大的顺序

16、依次向树中加边。 在添加每一条边（u，v）时，如果u和V两个点分别属于不同的两个集合(即两个点还没有连通，不在同一棵树上，否则加上就构成环)，那么就加入这条边，否则处理下一条边。 3、直到添加n-1条边。,1,2,4,3,5,17,30,10,24,7,23,5,1,2,3,4,5,Kruskal算法; sort; /排序边 for i:=1 to n do fi:=0; /初始化根为0 ans:=0; /价值 for i:=1 to m do union(ei); /加边,procedure union(p:node); /检查边p是否能加到生成树中 var x,y:integer; beg

17、in x:=find(p.u); /找u的根 y:=find(p.v); /找v的根 if xy then /不同根，构不成环，加入到树中 begin inc(ans, p.data); fy:=x; / 根合并 end; end;,function find(i:integer):integer; /查找i的父亲 begin if fi=0 then exit(i); /i是根 if ffi=0 then exit(fi); /i的父亲是根 find:=find(fi); /递归查找 fi:=find; /路径压缩 end;,一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞

18、数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如阵列: 0234500067103456050020456006710000000089有4个细胞。 输入：整数m,n(m行，n列=3000) M*n的矩阵，数据之间无空格； 输出：细胞的个数。,例2、细胞统计,0234500067103456050020456006710000000089,算法分析：,搜索可以实现（dfs，bfs）,dx:array1.4of integer=(1,0,-1,0); dy:array1.4of integer=(0,1,0,-1);,/逐行逐列扫描： ans:=0; for i:=1 to n

19、 do for j:=1 to m do if bi,j then begin inc(ans); try(i,j); end;,procedure try(i,j:integer);/dfs var k:integer; begin bi,j:=false;/访问标记 for k:=1 to 4 do if bi+dxk,j+dyk then try(i+dxk,j+dyk); end;,并查集实现, 逐行扫描，依次处理每一个点 初始化：每个点的父亲指向本身 /每个数是独立的一个细胞 处理点A(I,j): 3种情况如下： 如果B和C都是细胞：合并 P=find(c); q=find(b);

20、If pq then fatherp=q fatherA=q; 如果B是而C不是，则 fatherA=B 或fatherA=find(B) 如果B不是而C是，则 fatherA=C 或fatherA=find(C) 统计父亲是自身(find(i)=i)的结点数即细胞的个数,const maxn=3000; type point=record x,y:integer; /行与列 end; a:array1.maxn,1.maxnof point; /父亲结点 b:array0.maxn,0.maxnof boolean; /是否是细胞,算法的实现：,/数据读入 readln(n,m); for

21、i:=1 to n do begin for j:=1 to m do begin read(ch); bi,j:=ch0; if bi,j then begin ai,j.x:=i; ai,j.y:=j; end; / 初始化父亲指向自身 end; readln; end;,for i:=1 to n do for j:=1 to m do if bi,j then begin if bi-1,j and bi,j-1 then /左与上是细胞 begin p:=find(i-1,j); q:=find(i,j-1); if (p.xq.x)or(p.yq.y) then ap.x,p.y:

22、=q; ai,j:=q; end; if bi-1,jand not bi,j-1 then /上是左不是 begin ai,j.x:=i-1;ai,j.y:=j; end; if bi,j-1 and not bi-1,j then /上不是左是 begin ai,j.x:=i;ai,j.y:=j-1; end; end;,逐行扫描处理每个细胞结点,function find(x0,y0:longint):point; /查找当前位置（x0，y0）细胞的父亲结点 begin if (x0=ax0,y0.x) and (y0=ax0,y0.y) then exit(ax0,y0); find:

23、=find(ax0,y0.x,ax0,y0.y); ax0,y0:=find; /路径压缩 end;,/统计细胞的个数：父亲指向自己的结点数量 tot:=0; for i:=1 to n do for j:=1 to m do if (ai,j.x=i) and (ai,j.y=j) then inc(tot);,例3、房间问题（NOI94）,下图是一张建筑平面图，编程计算1、该建筑中有多少个房间；2、最大的房间有多大；3、拆除建筑中的某一堵墙，以形成一个尽可能大的房间。指出该墙。该建筑分成个方块（m50，n50），每个方块可有04堵墙（0表示无墙）。,输入数据：用一个数字表示一个方块。文件开

24、始是北南方向的方块数，其次是东西方向的方块数。后面的行中，每个方块中墙的特征由数字P来描述（0P15）。数字P是下面的可能取的数字之和：1（西墙 west）2（北墙 north）4（东墙 east）8（南墙 south）室内的墙被定义两次： 例如方块 （1， 1）中的南墙也被位于其南面的方块（2，1 ）定义了一次。建筑中至少有两个房间。在我们的例子中文件INPUT.TXT的内容为：输出数据：第1行写房间总数；第2行写最大房间的面积（方块数）；第3行写你的建议，指明应拆除位于哪两个方格间的一堵墙 第4行拆除后形成的最大房间面积。 在我们的例子中，第3行是 (3,3)(3,4)，这是各种解中的一个

25、，你只要给出其中一个即可。,样例输入： 4711 6 11 6 3 10 67 9 6 13 5 15 51 10 12 7 13 7 513 11 10 8 10 12 13,问题： 1、该建筑中有多少个房间；2、最大的房间有多大；3、拆除建筑中的某一堵墙，以形成一个尽可能大的房间。指出该墙。 4、拆除后形成的最大房间面积,输出： 59(3,3)(3,3) 16,7,9,3,8,1,算法分析：,类似细胞统计,第一问：该建筑中有多少个房间； 逐行扫描，处理当前格子与上方和左方的格子。最后统计,第二问：最大的房间有多大； 父亲格子设置一个统计格子数量的变量，每扫描到一个以当前格子为父亲的格子，数

26、量加1。,第三问：拆除建筑中的某一堵墙，以形成一个尽可能大的房间。指出该墙。 枚举每一堵墙 如果是竖直方向的墙：看左右是否连通，如果连通（同父亲），拆除后不改变面积；不连通则求左右两部分面积和，比较。 如果水平的墙：看上下两部分。,读入数据的处理技巧：, 怎样判断某个格子的四周墙的情况，哪个方向有墙？,格子的值是x；考察二进制数：1111 W:x mod 2=1; N:x div 2 mod 2=1; E:x div 4 mod 2=1; S:x div 8 mod 2=1;,样例输入： 4711 6 11 6 3 10 67 9 6 13 5 15 51 10 12 7 13 7 513 1

27、1 10 8 10 12 13,方法一： 用一个二维数组记下每个格子的数值aI,j，在使用时直接根据数值特征判断四周墙的情况。,方法二： 用布尔数组记下北墙和西墙的情况。,for i:=1 to n do for j:=1 to m do begin read(x); westi,j:=x mod 2=1; northi,j:= x div 2 mod 2=1; end;,readln(n); readln(m); for i:=1 to n do for j:=1 to m do begin read(x); westi,j:=x mod 2=1; northi,j:= x div 2 mo

28、d 2=1; end;,type node=record x,y:integer; end; var west,north:array1.max,1.max of boolean;/记录北西墙 square:array1.max,1.max of longint; /房间的面积 root:array1.max,1.max of node; /每个格子的父亲 n,m:integer; total,maxsquare,best:longint; /房间数量，最大房间面积，拆除某一墙后形成的房间面积 x,y:integer; /记录当前的格子 d:string;/记录拆除墙的方向,/读入格子的情况

29、procedure init; var i,j,x:integer; begin fillchar(west,sizeof(west),false); fillchar(north,sizeof(north),false); readln(n); readln(m); for i:=1 to n do for j:=1 to m do begin read(x); westi,j:=x mod 2=1; /有西墙 northi,j:= x div 2 mod 2=1;/有北墙 end; end;,/查找格子（i，j）的父亲格子 function find(i,j:integer):node;

30、begin if (rooti,j.x=i) and(rooti,j.y=j) then exit(rooti,j); if (rootrooti,j.x,rooti,j.y.x=rooti,j.x)and (rootrooti,j.x,rooti,j.y.y=rooti,j.y) then exit(rooti,j); find:=find(rooti,j.x,rooti,j.y); rooti,j:=find; end；,procedure makeroot; /处理每个格子，集合的合并过程 var i,j:integer; p,q:node; begin for i:=1 to n do

31、 for j:=1 to m do begin rooti,j.x:=i;rooti,j.y:=j;end; /格子父亲初始化。 for i:=1 to n do for j:=1 to m do begin if (not westi,j)and(not northi,j) then /左上没墙 begin p:=find(i,j-1); q:=find(i-1,j); if (p.xq.x)or(p.yq.y) then rootp.x,p.y:=q; rooti,j:=q; end; if (not westi,j)and(northi,j) then rooti,j:=find(i,j

32、-1);/左没，上有 if (westi,j)and(not northi,j) then rooti,j:=find(i-1,j);/左右，上没有 end; for i:=1 to n do for j:=1 to m do rooti,j:=find(i,j); /全部扫描,procedure work;/计算过程 var i,j:integer; begin fillchar(square,sizeof(square),0); total:=0; /房间数量 maxsquare:=0;/最大房间面积 for i:=1 to n do for j:=1 to m do begin if (

33、rooti,j.x=i) and (rooti,j.y=j) then inc(total);/统计根的数量 inc(squarerooti,j.x,rooti,j.y);/父亲面积加1 end; for i:=1 to n do /找最大房间面积 for j:=1 to m do if maxsquaresquarei,j then maxsquare:=squarei,j;,/判断拆除哪一个墙使房间面积变得最大 best:=0; for i:=1 to n do for j:=1 to m do begin / 拆当前格子的西墙 if (j1)and(rooti,j-1.xrooti,j.

34、x)or(rooti,j-1.yrooti,j.y)and (best1)and(rooti-1,j.xrooti,j.x)or(rooti-1,j.yrooti,j.y)and (bestsquarerooti-1,j.x,rooti-1,j.y+squarerooti,j.x,rooti,j.y) then begin best:=squarerooti-1,j.x,rooti-1,j.y +squarerooti,j.x,rooti,j.y; x:=i; y:=j; d:=N; /记下当前格子及北墙：上 end; end;,procedure print;/输出结果 begin assi

35、gn(output,fout);rewrite(output); writeln(total); writeln(maxsquare); if d=W then writeln(,x, ,y-1,),(,x, ,y,); if d=N then writeln(,x-1, ,y,),(,x, ,y,); writeln(best); close(output); end;,/主程序 BEGIN INIT; makeroot; WORK; print; END.,例4、二进制方程,【问题描述：】 一个形如：X1X2Xn=Y1Y2.Ym 的等式称为二进制方程。 在二进制方程的两边：Xi和Yj （1

36、=i=n；1=j=m）是二进制数字（0、1）或者一个变量（小写字母）。每个变量都是一个有固定长度的二进制代码，他可以在等式中取代变量的位置，称这个长度为变量的长度。为了解一个二进制方程，需要给其中的变量赋予适当的二进制代码，使得我们用他们替代等式中的相应的变量后（等式的两边都变成二进制代码），这个等式成立。 编程任务： 对于每一个给出的方程，计算一共有多少组解。已知变量最多有26个（26个英文小写字母），且等式的每一端的数字和变量的长度之和不超过10000。 【输入：】 第一行：k（k=26,变量的个数，规定使用小写英文字母中的前k个字母作为变量，如k=5，则变量a,b,c,d,e）。 第二行

37、：k个正整数，中间用一个空格隔开，依次代表k个变量的长度。 第三行：等式左边的表达式。 第四行：等式右边的表达式。 【输出：】 等式中出现的变量共有多少组解。,样例1输入： 2 4 2 1b1 a 样例1输出： 4 （说明： 两个变量：a，b 长度分别为：4 和2 4组解 1 、a=1001； b=00 2、 a=1011； b=01 3、 a=1101； b=10 4、 a=1111； b=11）,样例2输入： 5 4 2 4 4 2 1bad1 acbe 样例2输出： 16 （样例说明： K=5，变量：a,b,c,d,e。长度分别为：4 2 4 4 2。等式是：1bad1= acbe 输出

38、16，即变量a,b,c,d,e共有16组解。）,样例1输入： 2 4 2 1b1 a 样例1输出： 4 （说明： 两个变量：a，b 长度分别为：4 和2 4组解 1 、a=1001； b=00 2、 a=1011； b=01 3、 a=1101； b=10 4、 a=1111； b=11）,分析：,等式：1b1=a 可以写成等价的等式： 1 b1 b2 1=a1 a2 a3 a4 可以得到如下的等式：a1=1;a2=b1;a3=b2;a4=1。 a1,a4唯一确定， a2=b1,a3=b2有两个等价类，均可以取0和1两种情况。故有4组解。,样例2： 方程: 1bad1= acbe 写成等价式：

39、 1 b1 b2 a1 a2 a3 a4 d1 d2 d3 d4 1 =a1 a2 a3 a4 c1 c2 c3 c4 b1 b2 e1 e2 得出： 1=a1 b1=a2 b2=a3 a1=a4 a2=c1 a3=c2 a4=c3 d1=c4 d2=b1 d3=b2 d4=e1 1=e2 整理以上等式得出： 1=a1=a4=c3=e2 (确定) b1=a2=c5=d2 b2=a3=c2=d3 d1=c4 d4=e1 得到4个未知的等价类：每个等价类都有0和1两种情况： 故共有24=16组解。,样例2输入： 5 4 2 4 4 2 1bad1 acbe 样例2输出： 16,结论：,把每个长度为

40、k的变量为k个长度为1的变量，则结果不变。 这样我们可以得到n个等式（n为等号两边的长度）。 每个等式可以确定某两个变量相等，因此我们可以得到一系列的等价关系。 用并查集很容易在近似O(n)的时间复杂度下找到所有的等价类。只要不包含0和1的等价类取值均有两种情况。 因此如果等价类个个数为p，则2p就是解的个数。,p=n(10000),高精度运算,将等式的两边展开后，为了表示等价关系，我们可以将每个变量对应一个数值，以便于找等价关系：,0：0 1：1 a1：2 a2：3 a3：4 a4：5 b1：6 b2：7 .,样例2输入： 5 4 2 4 4 2 1bad1 acbe 样例2输出： 16,判

41、断等式,把等式中出现的变量与数值一一对应，根据等价关系：把变量相同等价成相应数值在同一集合的问题。 如：a2=b1对应：3和6在同一集合。 把变量的等价关系化为数值的等价关系，便于处理。,样例2输入： 5 4 2 4 4 2 1bad1 acbe 样例2输出： 16,0：0 1：1 a1：2 a2：3 a3：4 a4：5 b1：6 b2：7 c1: 8 c2: 9 c3: 10 c4: 11 d1: 12 d2: 13 d3: 14 d4: 15 e1: 16 e2: 17,样例2： 方程: 1bad1= acbe 写成等价式： 1 b1 b2 a1 a2 a3 a4 d1 d2 d3 d4

42、1 =a1 a2 a3 a4 c1 c2 c3 c4 b1 b2 e1 e2 得出： 1=a1 b1=a2 b2=a3 a1=a4 a2=c1 a3=c2 a4=c3 d1=c4 d2=b1 d3=b2 d4=e1 1=e2 整理以上等式得出： 1=a1=a4=c3=e2 (确定) b1=a2=c1=d2 b2=a3=c2=d3 d1=c4 d4=e1 对应数值的关系： 1=2=5=10=17 6=3=8=13 7=4=9=14 12=11 15=16,4个等价类,无解的情况： 1）等式两边转换后长度不相等。 2）0和1在同一集合内。 注意：集合内有0或1的解是唯一的，不能乘2,等式中没出现的

43、变量不应计算。,有5个变量：a,b,c,d,e。长度分别为：4 2 4 4 2。 等式：1b0=a 可以写成等价的等式：1 b1 b2 0=a1 a2 a3 a4 可以得到如下的等式：a1=1;a2=b1;a3=b2;a4=0。 给定的变量有abcde，但等式中仅涉及ab，所以有4组解 。 如果考虑cde则有212=4096组解。,type ab=array0.10001of longint; data=array0.3020 of integer;/高精度结果 var sa,sb:ab;变量的对应值 b:array0.max of boolean;标记该变量是否在等式中出现 len,sum,

44、l:longint; tot:data;,最大210000:10000*log(2)=3010,procedure init; var ta,tb,n,i:longint; ch:char; a:arraya.zof record start,long:longint; end; start：变量在sa，sb中出现的位置，long：变量的长度 procedure make(var sa:ab; var ta:longint); 把等式两边的表达式转化成对应的数值 var i:longint; ch:char; begin fillchar(b,sizeof(b),false); ta:=0;

45、while not eoln do begin read(ch); if (ch=0) or (ch=1) then begin inc(ta); sata:=ord(ch)-48; end else for i:=1 to ach.long do begin inc(ta); sata:=ach.start+i; bsata:=true;end; end; end;,BEGIN init assign(input,fin); reset(input); readln(n); sum:=1; for i:=1 to n do 定义变量的对应值 begin ch:=chr(96+i); ach.

46、start:=sum; read(ach.long); sum:=sum+ach.long; end; readln; make(sa,ta); readln; make(sb,tb); if tatb then tot1:=-1;长度不等时，无解 len:=ta; close(input); END;init,BEGIN work if tot1=-1 then begin print(0);exit;end; for i:=0 to sum do ai:=-1;集合初始化 for i:=1 to len do /len:等式的长度 begin p:=find(sai); q:=find(s

47、bi); if pq then ap:=q; 对应的变量如果不在一个集合则合并所在的集合 end; check; END.,procedure check; var i:longint; begin if find(0)=find(1) then 0和1在一个集合中，无解 begin print(0);exit; end; tot1:=1;l:=1; for i:=2 to sum do /统计等价类：集合的个数，从而求出解的组数:是根结点但又不包含0或者1的集合个数 if (find(i)=i) and bi and (ifind(0) and (ifind(1) then mul2; pr

48、int(1); end;,function find(i:longint):longint; 查找，路径压缩，合并集合 begin if ai=-1 then exit(i); find:=find(ai); ai:=find; end;,【问题描述】 公元五八一年，地球居民迁移至金牛座第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。 宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄

49、气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, , 30000。之后，他把自己的战舰也依次编号为1, 2, , 30000，让第i号战舰处于第i列(i = 1, 2, , 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。,例5、银河英雄传说（NOI2002）,然

50、而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。 在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。 最终的决战已经展开，银河的历史又翻过了一页,【输入文件】 输入文件galaxy.in的第一行有一个整数T（1=T=500,000），表示总共有T条指令。 以下有T行，每行有一条指令。指令有两种格式： M i j ：i和j是两个整数（1=i , j=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。 C i j ：i和j是两个整数（1=i , j=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。 【输出文件】 输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理： 如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但