并查集(最終版).ppt

1、并查集,JSOI2015冬令營,并查集基本概念 并查集基本操作 并查集應(yīng)用舉例,問題描述：或許你并不知道，你的某個(gè)朋友是你的親戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孫子！ 如果能得到完整的家譜，判斷兩個(gè)人是否親戚應(yīng)該是可行的，但如果兩個(gè)人的最近公共祖先與他們相隔好幾代，使得家譜十分龐大，那么檢驗(yàn)親戚關(guān)系實(shí)非人力所能及。在這種情況下，最好的幫手就是計(jì)算機(jī)。為了將問題簡(jiǎn)化，你將得到一些親戚關(guān)系的信息，如Marry和Tom是親戚，Tom和Ben是親戚，等等。從這些信息中，你可以推出Marry和Ben是親戚。,例1：親戚,輸入: 由兩部分組成： 第一部分以N，M開始。N為問題涉及的人的個(gè)數(shù)

2、。這些人的編號(hào)為1,2,3, N。下面有M行，每行有兩個(gè)數(shù)ai, bi，表示已知ai和bi是親戚。 第二部分以Q開始。以下Q行有Q個(gè)詢問，每行為ci, di，表示詢問ci和di是否為親戚。 輸出：對(duì)于每個(gè)詢問ci, di，輸出一行：若ci和di為親戚，則輸出“Yes”，否則輸出“No”。,請(qǐng)寫一個(gè)程序，對(duì)于我們的關(guān)于親戚關(guān)系的提問，以最快的速度給出答案。,輸入樣例（relation.in）： 10 7 2 4 5 7 1 3 8 9 1 2 5 6 2 3 3 3 4 7 10 8 9,輸出樣例（relation.out）： Yes No Yes,問題規(guī)模1： 1 N 255 1 M 1 00

3、0 000 1 Q 1 000 000,各抒己見,思路點(diǎn)拔,題意分析 算法及數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 時(shí)間、空間復(fù)雜度估計(jì)及實(shí)踐細(xì)節(jié)討論 優(yōu)化思路討論,輸入關(guān)系 分離集合 初始狀態(tài) 12345678910 (2,4) 12,435678910 (5,7) 12,435,768910 (1,3) 1,32,45,768910 (8,9) 1,32,45,768,910 (1,2) 1,2,3,45,768,910 (5,6) 1,2,3,45,6,78,910 (2,3) 1,2,3,45,6,78,910,實(shí)時(shí)判斷,集 合,定義及運(yùn)算：var s:set of 1.100; 集合與集合：交A*B、并A+B

4、、差A(yù)-B，結(jié)果還是集合； 關(guān)系運(yùn)算 相等=、不相等、包含于=，結(jié)果為boolean； 元素與集合：x in s，結(jié)果為boolean；,集合的優(yōu)缺點(diǎn)：容易理解，運(yùn)算簡(jiǎn)單； 數(shù)據(jù)量小、調(diào)試不方便；,問題規(guī)模2： 1 N 20000 1 M 1 000 000 1 Q 1 000 000,并查集,并查集（union-find set）是一種用于分離集合操作的抽象數(shù)據(jù)類型。它所處理的是“集合”之間的關(guān)系，即動(dòng)態(tài)地維護(hù)和處理集合元素之間復(fù)雜的關(guān)系，當(dāng)給出兩個(gè)元素的一個(gè)無序?qū)?a,b)時(shí)，需要快速“合并”a和b分別所在的集合，這其間需要反復(fù)“查找”某個(gè)元素所在的集合?！安ⅰ?、“查”和“集”三字由此而來

5、。在這種數(shù)據(jù)類型中，n個(gè)不同的元素被分為若干組。每組是一個(gè)集合，這種集合叫做分離集合（disjoint set）。并查集支持查找一個(gè)元素所屬的集合以及兩個(gè)元素各自所屬的集合的合并。,如何用已有的數(shù)據(jù)類型或數(shù)據(jù)結(jié)構(gòu)去構(gòu)造？,并查集本身不具有結(jié)構(gòu)，必須借助一定的數(shù)據(jù)結(jié)構(gòu)以得到支持和實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)的選擇是一個(gè)重要的環(huán)節(jié)，選擇不同的數(shù)據(jù)結(jié)構(gòu)可能會(huì)在查找和合并的操作效率上有很大的差別，但操作實(shí)現(xiàn)都比較簡(jiǎn)單高效。并查集的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)方法很多，一般用的比較多的是，數(shù)組實(shí)現(xiàn)、鏈表實(shí)現(xiàn)和樹實(shí)現(xiàn)。,并查集,并查集的數(shù)據(jù)結(jié)構(gòu)記錄了一組分離的動(dòng)態(tài)集合S，S=S1,S2,Sk，每個(gè)集合通過一個(gè)“代表”加以識(shí)別，代表即該

6、集合中的某個(gè)元素（成員），哪一個(gè)成員被選做代表是無所謂的，重要的是：如果求某一動(dòng)態(tài)集合的代表兩次，且在兩次請(qǐng)求間不修改此集合，則兩次得到的答案應(yīng)該是相同的。,動(dòng)態(tài)集合中的每一元素是由一個(gè)對(duì)象來表示的，設(shè)x表示一個(gè)對(duì)象，并查集的實(shí)現(xiàn)需要支持如下操作：,并查集的基本操作, MAKE-SET（x） 建立一個(gè)新的集合，其僅有的成員（同時(shí)就是代表）是x。由于各集合是分離的，所以要求x沒有在其它集合中出現(xiàn)過。 UNION（x,y） 將包含x和y的動(dòng)態(tài)集合（例如Sx和Sy）合并為一個(gè)新的集合，假定在此操作前這兩個(gè)集合是分離的。結(jié)果的集合代表是SxSy的某個(gè)成員。一般來說，在不同的實(shí)現(xiàn)中通常都以Sx或者Sy的

7、代表作為新集合的代表。此后，由新的集合S代替了原來的Sx和Sy。 FIND-SET（x） 返回一個(gè)包含x的集合的代表。,并查集的數(shù)組實(shí)現(xiàn),輸入樣例： 10 7 2 4 5 7 1 3 8 9 1 2 5 6 2 3 3 3 4 7 10 8 9,UNION（x,y）過程演示：,S,1 2 3 4 5 6 7 8 9 10,S,1 2 3 4 5 6 7 8 9 10,用數(shù)組si記錄元素i所屬集合的編號(hào)。 MAKE-SET（x）：初始化只要si：=i； FIND-SET（x）：查找元素所屬的集合時(shí)，只需讀出si，時(shí)間復(fù)雜度為O(1)。 UNION（x,y）：合并兩元素各自所屬的集合時(shí)，需要將數(shù)組

8、中屬于其中一個(gè)集合的元素所對(duì)應(yīng)的數(shù)組元素值全部改為另一個(gè)集合的編號(hào)值，時(shí)間復(fù)雜度為O(n)。 實(shí)現(xiàn)簡(jiǎn)單，實(shí)際使用較多。但是合并的代價(jià)太大，在最壞情況下，所有集合合并成一個(gè)集合的總代價(jià)會(huì)達(dá)到O(n2)。,每個(gè)集合對(duì)應(yīng)一個(gè)鏈表，它有一個(gè)表頭，每一個(gè)元素有一個(gè)指針指向表頭，表明了它所屬的類，另有一個(gè)指針指向它的下一個(gè)元素,同時(shí)為了方便實(shí)現(xiàn)，再設(shè)一個(gè)指針last表示鏈表中的最后一個(gè)元素（表尾）。 當(dāng)然，由于處理的對(duì)象一般都是連續(xù)整數(shù)，所以，可以選擇靜態(tài)數(shù)組（通過下標(biāo)）來模擬實(shí)現(xiàn)，如： type node = record head,next,last:integer; end; var S : arr

9、ay1.maxn of node;,并查集的鏈表實(shí)現(xiàn),MAKE-SET(x)：Sx.head = x;Sx.next = 0; FIND-SET(x)：return Sx.head; 兩個(gè)過程的時(shí)間復(fù)雜度都為O(1)。 采用鏈表時(shí)，當(dāng)有兩個(gè)元素(x,y),若FIND-SET（x） FIND-SET（y），則兩者對(duì)應(yīng)不同的集合，需要將兩個(gè)鏈表合并，做法是將一個(gè)表的表頭直接接到另一個(gè)表的表尾，這一步操作看似很簡(jiǎn)單，但勢(shì)必造成修改后需要把接上去的那個(gè)表的所有head值修改，這需要線性的賦值操作，其復(fù)雜度與選擇接在尾部的鏈表長度成正比。,UNION(x,y)： 假設(shè)UNION(x,y)的參數(shù)是有序的，

10、即把y屬于的集合合并到x的集合有兩種實(shí)現(xiàn)方法：,（1）簡(jiǎn)單實(shí)現(xiàn) 不考慮任何因素，出現(xiàn)FIND-SET（x） FIND-SET（y）時(shí)，直接將y的表頭接到x的表尾，同時(shí)將y中所在集合元素的head值設(shè)為FIND-SET(x)。同時(shí)x的表尾也應(yīng)該設(shè)為原y表的表尾。 注意：last指針其實(shí)只要在表頭結(jié)點(diǎn)中記錄即可，因?yàn)槊恳淮尾榈紽IND-SET（x）都可以得到表頭元素。而鏈表中其他元素重新記錄last是無意義的。 我們總是把y接到x里去，那么如果y所在的集合非常大，每次賦值的代價(jià)就會(huì)非常高，考慮輸入數(shù)據(jù)的特殊性，比如出現(xiàn)輸入為： （2，1），（3，1），（4，1），（5，1），（6，1） ， ，(n

11、,1) 最壞情況下時(shí)間復(fù)雜度為O(n2)。,（2）快速實(shí)現(xiàn) 上述簡(jiǎn)單實(shí)現(xiàn)非常不理想，針對(duì)y可能比較大的這個(gè)問題，可以很快產(chǎn)生一個(gè)聰明的想法：不妨比較x和y所在集合的大小，從而作出選擇，把較短的鏈表接在較長的尾部，這樣效果是一樣的，但耗費(fèi)肯定不比原來差。這就是快速實(shí)現(xiàn)的思路。可以在node里多設(shè)一個(gè)域number，用來記錄此條鏈表中成員的個(gè)數(shù)。顯然number記錄在表頭元素中即可，將兩表合并的時(shí)候，只要將表的number相加，因此維護(hù)起來是非常方便的。 這種快速實(shí)現(xiàn)的方法可以稱為加權(quán)啟發(fā)式合并，這里的權(quán)就是指所記錄的number。,可以證明這種方法的效率。當(dāng)有n個(gè)元素時(shí)，在UNION上的花費(fèi)（即

12、重新賦值的次數(shù)）的上界是O(nlog2n)。因?yàn)椋嚎紤]一個(gè)固定的對(duì)象x，當(dāng)x的代表指針（head）被更新時(shí)，x必是屬于一個(gè)較小的集合，因此，x的代表指針第一次更新后，結(jié)果集合必然至少有2個(gè)元素，類似的，下一次更新后，x所在的集合至少有4個(gè)元素。繼續(xù)下去，可以發(fā)現(xiàn)，x的代表指針最多被更新log2n次，因?yàn)楫?dāng)x所在集合元素已經(jīng)等于n以后，不可能再發(fā)生UNION操作。所以，總共有n個(gè)元素時(shí)，操作的總次數(shù)不超過nlog2n次。這就保證了整個(gè)算法的復(fù)雜度是理想的。,并查集的鏈表實(shí)現(xiàn)是一種非常容易接受的算法，并且它的效率也是令人滿意的。其實(shí)它的思路和數(shù)組完全一樣，所以實(shí)際使用較少。,合并兩個(gè)集合時(shí)的實(shí)現(xiàn)過

13、程如下： UNION(x,y) x = FIND-SET(x); y = FIND-SET(y); if x.numbery.number then UNION(x,y) else UNION(y,x); ,我們用有根樹來表示集合，樹中的每個(gè)節(jié)點(diǎn)包含集合的一個(gè)成員，每棵樹表示一個(gè)集合。多個(gè)集合形成森林態(tài)，以每棵樹的樹根作為集合的代表，并且根結(jié)點(diǎn)的父結(jié)點(diǎn)指向其自身，樹上的其他結(jié)點(diǎn)都用一個(gè)父指針表示它的附屬關(guān)系。 注意：在同一棵樹中的結(jié)點(diǎn)屬于同一個(gè)集合，雖然它們?cè)跇渲写嬖诟缸咏Y(jié)點(diǎn)關(guān)系，但并不意味著它們之間存在從屬關(guān)系。樹的指針起的只是聯(lián)系集合中元素的作用。 在并查集中，每個(gè)分離集合對(duì)應(yīng)的一棵樹，稱

14、為分離集合樹。整個(gè)并查集也就是一棵分離集合森林。,并查集的樹實(shí)現(xiàn),如下圖表示了這種關(guān)系，其包含兩個(gè)集合b,c,e,h,d,f,g分別以c和f作為代表。,這種樹結(jié)構(gòu)，也可以簡(jiǎn)單地用靜態(tài)數(shù)組實(shí)現(xiàn)，設(shè)px表示x元素所指向的父親。 MAKE-SET(x)：px=x; FIND-SET(x)：要從x開始，向上尋找它的父親，直到找到根為止。 UNION（x,y）：只要使一棵樹的根指向另一棵樹的根，即成為一棵子樹。,1查找一個(gè)元素所屬的集合 在分離集合森林中，每一棵分離集合樹對(duì)應(yīng)一個(gè)集合。要查找某一元素所屬的集合，就是要找這個(gè)元素對(duì)應(yīng)的結(jié)點(diǎn)所在的分離集合樹。,查找樹的根結(jié)點(diǎn)的方法很簡(jiǎn)單，只需任取樹中一結(jié)點(diǎn)（

15、不妨就取我們要查找的那個(gè)結(jié)點(diǎn)），沿父結(jié)點(diǎn)方向一直往樹根走：初始時(shí)，取一個(gè)結(jié)點(diǎn)，走到它的父結(jié)點(diǎn)，然后以父結(jié)點(diǎn)為基點(diǎn)，走到父結(jié)點(diǎn)的父結(jié)點(diǎn)直至走到一個(gè)沒有父結(jié)點(diǎn)的結(jié)點(diǎn)為止，這個(gè)結(jié)點(diǎn)就是樹的根結(jié)點(diǎn)。如圖，描述了查找一個(gè)結(jié)點(diǎn)的過程（黑色結(jié)點(diǎn)為當(dāng)前查找結(jié)點(diǎn)）。,2兩個(gè)元素各自所屬的集合的合并 在分離集合森林中，分離集合是用分離集合樹來表示的。要合并兩個(gè)元素各自所屬的集合，也就是合并兩元素所對(duì)應(yīng)的兩個(gè)結(jié)點(diǎn)各自所在的分離集合樹。,考慮到在分離集合森林中，只要結(jié)點(diǎn)屬于同一棵樹，即被視為在同一個(gè)集合中，而不管具體是如何相連的。那么，我們只需簡(jiǎn)單的將一棵分離集合樹作為另一棵的子樹，即可使兩棵樹合并為一棵。如圖，描述

16、的是將兩棵分離集合樹D1和D2合并的過程（D1作為D2的根結(jié)點(diǎn)的一棵子樹）。,3優(yōu)化查找與合并算法 優(yōu)化合并過程 如果兩棵分離集合樹A和B，深度分別為hA和hB，則若hAhB，應(yīng)將 B樹作為A樹的子 樹；否則，將A樹 作為B樹的子樹。,優(yōu)化查找過程 對(duì)于查找過程有兩個(gè)方面的啟發(fā)式方法都很有效，分別是按秩合并和路徑壓縮優(yōu)化。 A按秩合并 進(jìn)行UNION的時(shí)候，只要讓具有較小秩的根指向具有較大秩的根。如果兩根的秩相等，只要使其中一個(gè)根指向另一個(gè)，同時(shí)秩應(yīng)當(dāng)增加1。這十分類似于統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)，但這里統(tǒng)計(jì)的是樹的深度。,B路徑壓縮優(yōu)化方法 在查找一個(gè)結(jié)點(diǎn)所在樹的根結(jié)點(diǎn)的過程中，要經(jīng)過一條從待查結(jié)點(diǎn)到根結(jié)

17、點(diǎn)的路徑。我們不妨就讓這些路徑上的結(jié)點(diǎn)直接指向根結(jié)點(diǎn)，作為根結(jié)點(diǎn)的子結(jié)點(diǎn)。這樣，這些路徑上的結(jié)點(diǎn)仍在分離集合中，整棵樹仍然滿足分離集合樹的要求，而路徑上的結(jié)點(diǎn)的深度無疑降低了，這些點(diǎn)及其子樹上的結(jié)點(diǎn)的查找復(fù)雜度大大降低。,如圖，描述了在一棵分離集合樹查找結(jié)點(diǎn)7的前后所呈現(xiàn)出的結(jié)構(gòu)。,優(yōu)化后的代碼： MAKE-SET(x) px=x；rankx=0； UNION(x,y) x = FIND-SET(x)；y=FIND-SET(Y)； if rankx ranky then py=x else px=y； if rankx = ranky then ranky = ranky+1; FIND-SE

18、T(x) if xpx then px=FIND-SET(px)； return px； ,并查集的應(yīng)用,簡(jiǎn)單模型基本應(yīng)用 優(yōu)化算法整合應(yīng)用 創(chuàng)新模型綜合應(yīng)用,例2：可愛的猴子(POI2003),一棵樹上有n 只猴子，他們從1到n編號(hào)。編號(hào)為1 的猴子用它的尾巴盤住了一個(gè)樹枝，剩下的猴子要么被其他的猴子鉤住要么就是自己用手鉤住其他的猴子。每只猴子都可以用兩只手去鉤其他的猴子,每只手最多只能鉤一只。從0時(shí)刻開始,每一秒都有一只猴子松開它的一只手。這也許會(huì)造成一些猴子掉落到地上,我們想要知道它們掉落地上的時(shí)間(猴子掉落的速度都非常的快,可以忽略掉落的時(shí)間)。,輸入： 第一行包含兩個(gè)整數(shù)n和 m,

19、1 = n = 200000, 1 = m = 400000。整數(shù) n 代表猴子總數(shù), 數(shù) m 代表我們觀察猴子的總時(shí)間。接下來 n 行描述初始的情形，第 (k + 1) 行 (1 = k = n) 有兩個(gè)整數(shù)分別代表猴子k的左手和右手分別抓住了哪兩只猴子，-1 代表它的那只手是空的。 接下來m行代表我們觀察到的猴子的活動(dòng)，第i行有兩個(gè)整數(shù)(1 = i = m) 代表在第i 1時(shí)刻放開手的是哪只猴子和它放開的是哪只手(1 左, 2 右)。,輸出： 輸出n個(gè)整數(shù)每行一個(gè)代表每只猴子掉落到地 上的時(shí)間, 如果沒有掉落, 輸出-1. 輸入樣例： 3 2-1 33 -11 21 23 1 輸出樣例：

20、-111,例3：優(yōu)化kruskal算法,Kruskal算法是一種貪心的求最小生成樹的算法，具體操作是初始時(shí)所有的邊都是未選邊，圖中只有點(diǎn)，每次選擇一條權(quán)值最小的，連接在不同連通塊的未選邊，然后將這條未選邊賦值為已選邊。 經(jīng)過n-1次操作之后，就求出了該圖的最小生成樹,例4：Ant Trip(HDU3018),Ant Country有N個(gè)小鎮(zhèn)，小鎮(zhèn)之間有M條路相連。Ant Tony和朋友們一起想游遍國內(nèi)所有的小鎮(zhèn)，對(duì)于每條路他們計(jì)劃都要走一遍且只走一遍。然而，這對(duì)于一個(gè)團(tuán)隊(duì)來說，是一個(gè)幾乎不可能完成的任務(wù)。因此，他們將分成若干個(gè)小組同時(shí)進(jìn)行，每個(gè)小組可以從不同的小鎮(zhèn)開始旅游，現(xiàn)在，tony 想知

21、道最少需要幾個(gè)小組就可以完成這個(gè)旅游計(jì)劃。,輸入： 輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)之間用一些空行間隔，每組數(shù)據(jù)的第一行有兩個(gè)整數(shù)N(1=N=100000),M(0=M=200000),表示Ant Country有N個(gè)小鎮(zhèn)和M條路，接下來有M行，每行有兩個(gè)整數(shù)a,b,(1=a,b=N)表示小鎮(zhèn) a和小鎮(zhèn)b有一條路。沒有兩條相同的路，也沒有一條路連接同一個(gè)小鎮(zhèn)。 對(duì)于沒有路連接的小鎮(zhèn)，將直接忽略它。,輸出：對(duì)于每組數(shù)據(jù)，輸出完成旅游計(jì)劃至少需要的小組數(shù)。 輸入樣例： 3 3 1 2 2 3 1 3 4 2 1 2 3 4,輸出樣例： 1 2,例5：銀河英雄傳說(NOI2002),宇宙歷七九九年，銀河系

22、的兩大軍事集團(tuán)在巴米利恩星域爆發(fā)戰(zhàn)爭(zhēng)。泰山壓頂集團(tuán)派宇宙艦隊(duì)司令萊因哈特率領(lǐng)十萬余艘戰(zhàn)艦出征，氣吞山河集團(tuán)點(diǎn)名將楊威利組織麾下三萬艘戰(zhàn)艦迎敵。 楊威利擅長排兵布陣，巧妙運(yùn)用各種戰(zhàn)術(shù)屢次以少勝多，難免恣生驕氣。在這次決戰(zhàn)中，他將巴米利恩星域戰(zhàn)場(chǎng)劃分成30000列，每列依次編號(hào)為1, 2, , 30000。之后，他把自己的戰(zhàn)艦也依次編號(hào)為1, 2, , 30000，讓第i號(hào)戰(zhàn)艦處于第i列(i = 1, 2, , 30000)，形成“一字長蛇陣”，誘敵深入。這是初始陣形。當(dāng)進(jìn)犯之?dāng)车竭_(dá)時(shí)，楊威利會(huì)多次發(fā)布合并指令，將大部分戰(zhàn)艦集中在某幾列上，實(shí)施密集攻擊。合并指令為M i j，含義為讓第i號(hào)戰(zhàn)艦所在

23、的整個(gè)戰(zhàn)艦隊(duì)列，作為一個(gè)整體（頭在前尾在后）接至第j號(hào)戰(zhàn)艦所在的戰(zhàn)艦隊(duì)列的尾部。顯然戰(zhàn)艦隊(duì)列是由處于同一列的一個(gè)或多個(gè)戰(zhàn)艦組成的。合并指令的執(zhí)行結(jié)果會(huì)使隊(duì)列增大。,然而，老謀深算的萊因哈特早已在戰(zhàn)略上取得了主動(dòng)。在交戰(zhàn)中，他可以通過龐大的情報(bào)網(wǎng)絡(luò)隨時(shí)監(jiān)聽楊威利的艦隊(duì)調(diào)動(dòng)指令。 在楊威利發(fā)布指令調(diào)動(dòng)艦隊(duì)的同時(shí)，萊因哈特為了及時(shí)了解當(dāng)前楊威利的戰(zhàn)艦分布情況，也會(huì)發(fā)出一些詢問指令：C i j。該指令意思是，詢問電腦，楊威利的第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦當(dāng)前是否在同一列中，如果在同一列中，那么它們之間布置有多少戰(zhàn)艦。 作為一個(gè)資深的高級(jí)程序設(shè)計(jì)員，你被要求編寫程序分析楊威利的指令，以及回答萊因哈特的詢問。,

24、輸入: 輸入文件galaxy.in的第一行有一個(gè)整數(shù) T（1=T=500,000），表示總共有T條指令。以下有T行，每行有一條指令。指令有兩種格式： M i j ：i和j是兩個(gè)整數(shù)（1=i , j=30000），表示指令涉及的戰(zhàn)艦編號(hào)。該指令是萊因哈特竊聽到的楊威利發(fā)布的艦隊(duì)調(diào)動(dòng)指令，并且保證第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦不在同一列。 C i j ：i和j是兩個(gè)整數(shù)（1=i , j=30000），表示指令涉及的戰(zhàn)艦編號(hào)。該指令是萊因哈特發(fā)布的詢問指令。,輸出: 輸出文件為galaxy.out。你的程序應(yīng)當(dāng)依 次對(duì)輸入的每一條指令進(jìn)行分析和處理： 如果是楊威利發(fā)布的艦隊(duì)調(diào)動(dòng)指令，則表示艦 隊(duì)排列發(fā)生了變化，你的程序要注意到這一點(diǎn)， 但是不要輸出任何信息； 如果是萊因哈特發(fā)布的詢問指令，你的程序要 輸出一行，僅包含一個(gè)整數(shù)，表