南工大第四章-圖

數(shù)據(jù)結(jié)構(gòu)與算法上機作業(yè)第四章圖一、選擇題1、在一個無向圖中,所有頂點得度數(shù)之與等于所有邊數(shù)得C倍。 A、1/2 B、1 C、2 D、42、在一個有向圖中,所有頂點得入度之與等于所有頂點出度之與得B倍。 A、1/2 B、1 C、2 D、43、G就是一個非連通無向圖,共有28條邊,則該圖至少有D個頂點。 A、6 B、7 C、8 D、94、有n個頂點得圖得鄰接矩陣使用B數(shù)組存儲得。 A、一維 B、n行n列 C、任意行n列 D、n行任意列5、對于一個具有n個頂點與e條邊得無向圖,采用鄰接表表示,則表頭數(shù)組大小至少為(假設(shè)下標為0得數(shù)組參與使用)A。 A、n-1 B、n+1 C、n D、n+e6、下列說法正確得就是C。 A、有向圖得鄰接矩陣一定就是不對稱得 B、有向圖得鄰接矩陣一定就是對稱得 C、無向圖得鄰接矩陣一定就是對稱得 D、無向圖得鄰接矩陣可以不對稱7、深度優(yōu)先遍歷類似與二叉樹得A:A、先根遍歷 B、中根遍歷 C、后根遍歷 D、層次遍歷8、廣度優(yōu)先遍歷類似與二叉樹得D:A、先根遍歷 B、中根遍歷 C、后根遍歷 D、層次遍歷9、下列關(guān)于開放樹(FreeTree)得說法錯誤得就是C:A、具有n個結(jié)點得開放樹包含n-1條邊B、開放樹沒有回路C、開放樹可以就是非連通圖D、在開放樹中任意加一條邊,一定會產(chǎn)生回路10、在如下圖所示得圖中,從頂點a出發(fā),按深度優(yōu)先遍歷,則可能得到得一種頂點得序列為。A、a,b,e,c,d,f B、a,c,f,e,b,dC、a,e,b,c,f,d D、a,e,d,f,c,b11、在如上圖所示得圖中,從頂點a出發(fā),按廣度優(yōu)先遍歷,則可能得到得一種頂點得序列為。 A、a,b,e,c,d,f B、a,b,e,c,f,d C、a,e,b,c,f,d D、a,e,d,f,c,b12、設(shè)網(wǎng)(帶權(quán)得圖)有n個頂點與e條邊,則采用鄰接表存儲時,求最小生成樹得Prim算法得時間復雜度為C。 A、O(n) B、O(n+e) C、O(n2) D、O(n3)13、設(shè)圖有n個頂點與e條邊,求解最短路徑得Floyd算法得時間復雜度為O。 A、O(n) B、O(n+e) C、O(n2) D、O(n3)14、最小生成樹就是指C。 A、由連通網(wǎng)所得到得邊數(shù)最少得生成樹。 B、由連通網(wǎng)所得到得頂點數(shù)相對較少得生成樹。 C、連通網(wǎng)中所有生成樹中權(quán)值之與為最小得生成樹。 D、連通網(wǎng)得極小連通子圖。15、下面關(guān)于工程計劃得AOE網(wǎng)得敘述中,不正確得就是B。 A、關(guān)鍵活動不按期完成就會影響整個工程得完成時間。 B、任何一個關(guān)鍵活動提前完成,那么整個工程將會提前完成。 C、所有關(guān)鍵活動都提前完成,那么整個工程將會提前完成。 D、某些關(guān)鍵工程若提前完成,那么整個工程將會提前完成。16、在AOE網(wǎng)中,始點與匯點得個數(shù)為C。A、1個始點,若干個匯點 B、若干個始點,若干個匯點C、若干個始點,1個匯點 C、1個始點,1個匯點17、在下圖所示得無向圖中,從頂點v1開始采用Prim算法生成最小生成樹,算法過程中產(chǎn)生得頂點次序為B。 A、v1,v3,v4,v2,v5,v6 B、v1,v3,v6,v2,v5,v4 C、v1,v2,v3,v4,v5,v6 D、v1,v3,v6,v4,v2,v518、在上圖所示得途中,采用Cruskal算法生成最小生成樹,過程中產(chǎn)生得邊得次序就是C。 A、(v1,v2),(v2,v3),(v5,v6),(v1,v5) B、(v1,v3),(v2,v6),(v2,v5),(v1,v4) C、(v1,v3),(v2,v5),(v3,v6),(v4,v5) D、(v2,v5),(v1,v3),(v5,v6),(v4,v5) 19、如下圖所示得圖中,其中一個拓撲排序得結(jié)果就是A。 A、v1→v2→v3→v6→v4→v5→v7→v8 B、v1→v2→v3→v4→v5→v6→v7→v8C、v1→v6→v4→v5→v2→v3→v7→v8D、v1→v6→v2→v3→v7→v8→v4→v520、在下圖所示得AOE網(wǎng)中,活動a9得最早開始時間為B。 A、13 B、14 C、15 D、1621、在上圖所示得AOE網(wǎng)中,活動a4得最遲開始時間為D A、2 B、3 C、4 D、522、設(shè)圖有n個頂點與e條邊,當用鄰接表表示該圖時,則求解最短路徑得Dijkstra算法得時間復雜度為O。 A、O(n) B、O(n+e) C、O(e) D、O(n2)二、填空題1、若無向圖G中頂點數(shù)為n,則圖G至多有n(n-1)/2條邊;若G為有向圖,則圖G至多有n(n-1)條邊。2、圖得存儲結(jié)構(gòu)主要有兩種,分別就是鄰接表與鄰接矩陣。3、若G就是有向圖,則把鄰接到頂點v得頂點數(shù)目或邊數(shù)目稱為頂點v得入度;把鄰接于頂點v得頂點數(shù)目或邊數(shù)目稱為頂點v得出度。4、已知一個圖得鄰接矩陣表示,計算第j個頂點得入度得方法就是第j行非0元素得個數(shù),計算第j個頂點得出度得方法就是第j列非0元素得個數(shù)。5、若將圖中得每條邊都賦予一個權(quán),則稱這種帶權(quán)得圖為網(wǎng)絡(luò)。6、無論就是有向圖還就是無向圖,頂點數(shù)n、邊數(shù)e與各頂點得度D(vi)之間得關(guān)系為:。7、若路徑上第一個頂點v1與最后一個頂點vm重合,則稱這樣得簡單路徑為回路或環(huán)。8、如果圖中任意一對頂點都就是連通得,則稱此圖就是連通圖;非連通圖得極大連通子圖叫做連通分量。9、創(chuàng)建一個鄰接矩陣圖得復雜度就是O(n*n);創(chuàng)建一個鏈接表圖得復雜度就是O(n+e)。10、圖得遍歷有深度優(yōu)先遍歷與廣度優(yōu)先遍歷等方法。11、在深度優(yōu)先搜索與廣度優(yōu)先搜索中,都采用visited[i]=0(false)得方式設(shè)置第i個頂點為new,而采用visited[i]=1(true)得方式標識第i個結(jié)點為old。12、由于深度優(yōu)先算法得特點,深度優(yōu)先往往采用遞歸得方式實現(xiàn)。13、由于廣度優(yōu)先算法得特點,在廣度優(yōu)先實現(xiàn)過程中,往往要借助于另一種數(shù)據(jù)結(jié)構(gòu)隊列實現(xiàn)。14、在深度優(yōu)先搜索與廣度優(yōu)先搜索中,在搜索過程中所經(jīng)過得邊都稱為搜索邊。15、連通而且無環(huán)路得無向圖稱為開放數(shù)。16、對于含有n個頂點e條邊得連通圖,利用Prim算法求其最小生成樹得時間復雜度為O(n*n),利用Kruscal算法求最小生成樹得時間復雜度就是O(e*lge)。3、頂點表示活動得網(wǎng)簡稱為AOV;邊表示活動得網(wǎng)簡稱為AOE。17、一個含有n個頂點得無向連通圖,其每條邊得權(quán)重都就是a(a>0),則其最小生成樹得權(quán)重等于(n-1)*a。18、具有n個頂點得有向圖,如果采用鄰接矩陣表示該圖,則求某頂點到其她各頂點得最短路徑得Dijkstra算法得時間復雜度就是O(n*n);如果采用鄰接表表示該圖,則時間復雜度為O(e)。19、在用Dijkstra算法求單源最短路徑得過程中,將頂點集合V劃分為兩個集合S與V-S,其中S中得點為最短路徑已確定得頂點集合,V-S中得點為最短路徑未確定得頂點集合。20、求每一對頂點之間得最短路徑,可以用兩種方法,一種就是分別對每個頂點采用算法,另一種方法就是。21、假設(shè)有向圖得鄰接矩陣C得傳遞閉包為A,則A[i][j]=1表示。22、有向圖得中心點就是指具有最小偏心度得頂點。三、已知一個無向圖如下圖所示,試給出該圖得鄰接矩陣與鄰接表存儲示意圖(畫圖,分別用矩陣與數(shù)組鏈表圖表示),并編程分別實現(xiàn)該圖得鄰接矩陣表示與鄰接表表示,要求編寫兩種表示方法得存儲結(jié)構(gòu)、相關(guān)基本操作,并在主函數(shù)中創(chuàng)建該圖。代碼:#include<iostream>usingnamespacestd;#definemax_vexNum26//最大頂點個數(shù)typedefstruct{intvex_num,arc_num;//頂點數(shù),邊數(shù)intcount;//記錄當前頂點數(shù)charvexs[max_vexNum];//頂點向量doublearcs[max_vexNum][max_vexNum];//鄰接矩陣}Graph;//添加一個新得頂點charNewNode(Graph*G,charv){ G->vexs[G->count]=v; G->count++; returnv;}//尋找某個頂點得位置intFindPosition(Graph*G,charv){ for(inti=0;i<G->count;i++){ if(v==G->vexs[i]) returni; }}voidDelete(Graph*G,charv){ //先刪除點 inti,j; inttemp_count=G->count;i=FindPosition(G,v); for(j=i;j<temp_count;j++) G->vexs[j]=G->vexs[j+1]; G->count--; //刪除邊 //先刪除行 intp=i;//記住位置 for(i=p;i<temp_count-1;i++) for(j=0;j<temp_count;j++) G->arcs[i][j]=G->arcs[i+1][j]; //再刪除列 for(i=p;i<temp_count-1;i++) for(j=0;j<temp_count;j++) G->arcs[j][i]=G->arcs[j][i+1];}//建立v1與v2得一條邊voidSetSoucc(Graph*G,charv1,charv2){ //先找到對應得定得位置 inti,j; inttemp_count=G->count; i=FindPosition(G,v1); j=FindPosition(G,v2); if(i==temp_count||j==temp_count)//沒有找到 return; //找到后,A[i][j]=0;vexs[j][i]=0; G->arcs[i][j]=1; G->arcs[j][i]=1;}voidDelSucc(Graph*G,charv1,charv2){ inti,j; inttemp_count=G->count; i=FindPosition(G,v1); j=FindPosition(G,v2); if(i==temp_count||j==temp_count)//沒有找到 return; //找到后,A[i][j]=0;vexs[j][i]=0; G->arcs[i][j]=0; G->arcs[j][i]=0;}//判斷v1y與v2就是否連接boolisEdge(Graph*G,charv1,charv2){ inti,j; inttemp_count=G->count; i=FindPosition(G,v1); j=FindPosition(G,v2); if(i==temp_count||j==temp_count)//沒有找到 return-1; if(G->arcs[i][j]==1) returntrue; returnfalse; }voidPrint(Graph*G){ inti,j; for(i=0;i<G->count;i++){ for(j=0;j<G->count;j++) cout<<G->arcs[i][j]<<""; cout<<endl; } cout<<endl;}Graph*G=newGraph;//初始化intmain(){ G->count=0; NewNode(G,'A'); NewNode(G,'B');NewNode(G,'C'); NewNode(G,'D'); //插入邊 SetSoucc(G,'A','B'); SetSoucc(G,'A','D'); SetSoucc(G,'C','B'); Print(G); //刪除一個頂點 Delete(G,'C'); Print(G); //刪除邊 DelSucc(G,'A','D'); Print(G); if(isEdge(G,'A','B')) cout<<"A與B右邊"<<endl; return0;}四、已知一個有向圖如下圖所示,試給出圖得鄰接矩陣與鄰接表存儲示意圖(畫圖,分別用矩陣與數(shù)組鏈表圖表示),并編程分別實現(xiàn)該圖得鄰接矩陣表示與鄰接表表示,要求編寫兩種表示方法得存儲結(jié)構(gòu)、相關(guān)基本操作,并在主函數(shù)中創(chuàng)建該圖。代碼:#include<iostream>#include<stdio、h>#include<stdlib、h>usingnamespacestd;#definemax_n20structArcNode{ charadjvex='#'; ArcNode*next=NULL;};typedefstructVNode{ chardata; ArcNode*first_head;}VNode,AdjList[max_n];typedefstruct{ AdjListvertices; intvexnum,arcnum; intcount=0;}Graph;//新增一個頂點charNewNode(Graph*G,charv){ G->vertices[G->count]、data=v; G->vertices[G->count]、first_head=newArcNode; G->count++; returnv;}//尋找某個頂點得位置intFindPosition(Graph*G,charv){ for(inti=0;i<G->count;i++){ if(v==G->vertices[i]、data) returni; }}//刪除一個頂點voidDelNode(Graph*G,charv){ inti=FindPosition(G,v); //去頭 ArcNode*p=G->vertices[i]、first_head; //現(xiàn)在vertices中刪除 intj; for(j=i;j<G->count-1;j++) G->vertices[j]=G->vertices[j+1]; G->vertices[j]、data='#'; G->vertices[j]、first_head=NULL; G->count--; //刪除邊 ArcNode*q; while(p!=NULL){ q=p; p=p->next; q=NULL; }}//設(shè)置v1到v2直接得一條邊voidSetSucc(Graph*G,charv1,charv2){ inti=FindPosition(G,v1); ArcNode*p; p=G->vertices[i]、first_head; while(p->next!=NULL){ p=p->next; }ArcNode*q=newArcNode; q->adjvex=v2; p->next=q;}ArcNode*FindNode(ArcNode*p,charv2){for(;p;p=p->next){if(p->next->adjvex==v2)break;}returnp;}voidDetele(Graph*G,charv1,charv2){ inti=FindPosition(G,v1); ArcNode*p; //沒有找到 if(i==-1) return; p=FindNode(G->vertices[i]、first_head,v2); //因為p就是上一個節(jié)點得位置,用q來保存//要刪除得節(jié)點得地址ArcNode*q=p->next;//通過將上一個節(jié)點得next指針指向要刪除節(jié)點得next指//針志向得節(jié)點實現(xiàn)斷開要刪除節(jié)點得目得//p->adjvex=p->next->adjvex;p->next=p->next->next;//刪除要刪除得節(jié)點qdeleteq;}//輸出領(lǐng)接表voidPrint(Graph*G){ ArcNode*p; for(inti=0;i<G->count;i++){ //先將data cout<< G->vertices[i]、data<<"->"; //從每個頂點得頭結(jié)點開始遍歷 if(G->vertices[i]、first_head->next!=NULL){ p=G->vertices[i]、first_head->next; while(p!=NULL){ cout<<p->adjvex<<"->"; p=p->next; } } cout<<endl; }cout<<endl;}Graph*G=newGraph;intmain(){ NewNode(G,'A'); NewNode(G,'B'); NewNode(G,'C'); NewNode(G,'D');Print(G);SetSucc(G,'A','D');SetSucc(G,'A','B');SetSucc(G,'A','C');SetSucc(G,'B','C');SetSucc(G,'C','D');SetSucc(G,'D','B');Print(G);Detele(G,'A','C');Detele(G,'D','B');Print(G);SetSucc(G,'D','C');Print(G); return0;}五、已知一個圖得頂點集為{a,b,c,d,e},其鄰接矩陣如下圖,考慮圖為無向圖與有向圖兩種情況,分別畫出該圖。六、已知一個連通圖如下圖所示,分別給出一個按深度優(yōu)先遍歷與廣度優(yōu)先遍歷得頂點序列(假設(shè)從頂點v1出發(fā))。并編程分別實現(xiàn)該圖得鄰接矩陣表示與鄰接表表示,要求編寫相關(guān)基本操作,并在主函數(shù)中求出深度優(yōu)先序列與廣度優(yōu)先序列。代碼:#include<iostream>#include<stdio、h>#include<stdlib、h>#include<queue>usingnamespacestd;#definemax_n20structArcNode{ charadjvex='#'; ArcNode*next=NULL;};typedefstructVNode{ chardata; ArcNode*first_head;}VNode,AdjList[max_n];typedefstruct{ AdjListvertices; intvisit[max_n]={0};//記錄就是否被訪問過 intvexnum,arcnum; intcount=0;}Graph;//新增一個頂點charNewNode(Graph*G,charv){ G->vertices[G->count]、data=v; G->vertices[G->count]、first_head=newArcNode; G->count++; returnv;}//尋找某個頂點得位置intFindPosition(Graph*G,charv){ for(inti=0;i<G->count;i++){ if(v==G->vertices[i]、data) returni; }}//刪除一個頂點voidDelNode(Graph*G,charv){ inti=FindPosition(G,v); //去頭 ArcNode*p=G->vertices[i]、first_head; //現(xiàn)在vertices中刪除 intj; for(j=i;j<G->count-1;j++) G->vertices[j]=G->vertices[j+1]; G->vertices[j]、data='#'; G->vertices[j]、first_head=NULL; G->count--; //刪除邊 ArcNode*q; while(p!=NULL){ q=p; p=p->next; q=NULL; }}//設(shè)置v1到v2直接得一條邊voidSetSucc(Graph*G,charv1,charv2){ inti=FindPosition(G,v1); ArcNode*p; p=G->vertices[i]、first_head; while(p->next!=NULL){ p=p->next; } ArcNode*q=newArcNode; q->adjvex=v2; p->next=q;}//對于無向圖voidSetSucc1(Graph*G,charv1,charv2){ SetSucc(G,v1,v2); SetSucc(G,v2,v1);}ArcNode*FindNode(ArcNode*p,charv2){ for(;p;p=p->next){ if(p->next->adjvex==v2) break; } returnp;}voidDetele(Graph*G,charv1,charv2){ inti=FindPosition(G,v1); ArcNode*p; //沒有找到 if(i==-1) return; p=FindNode(G->vertices[i]、first_head,v2); //因為p就是上一個節(jié)點得位置,用q來保存 //要刪除得節(jié)點得地址 ArcNode*q=p->next; //通過將上一個節(jié)點得next指針指向要刪除節(jié)點得next指 //針志向得節(jié)點實現(xiàn)斷開要刪除節(jié)點得目得//p->adjvex=p->next->adjvex; p->next=p->next->next; //刪除要刪除得節(jié)點q deleteq;}//輸出領(lǐng)接表voidPrint(Graph*G){ ArcNode*p; for(inti=0;i<G->count;i++){ //先將data cout<< G->vertices[i]、data<<"->"; //從每個頂點得頭結(jié)點開始遍歷 if(G->vertices[i]、first_head->next!=NULL){ p=G->vertices[i]、first_head->next; while(p!=NULL){ cout<<p->adjvex<<"->"; p=p->next; } } cout<<endl; } cout<<endl;}voidmakeVisitNull(Graph*G){ for(inti=0;i<max_n;i++) G->visit[i]=0;}voidDfs_part(Graph*G,inti){ ArcNode*p=G->vertices[i]、first_head->next; for(;p;p=p->next){ inti=FindPosition(G,p->adjvex); if(!G->visit[i]){ G->visit[i]=1; cout<<p->adjvex<<"->"; Dfs_part(G,i); } }}//深度優(yōu)先遍歷voidDFS(Graph*G,inti){ cout<<G->vertices[i]、data<<"->"; G->visit[i]=1; Dfs_part(G,i); //恢復 makeVisitNull(G);cout<<endl;}queue<int>qList;voidBfs_part(Graph*G){intt= qList、front(); cout<<G->vertices[t]、data<<"->"; qList、pop(); ArcNode*p=G->vertices[t]、first_head->next; for(;p;p=p->next){ inti=FindPosition(G,p->adjvex); if(!G->visit[i]){ G->visit[i]=1; qList、push(i); } } if(!qList、empty()) Bfs_part(G);}//voidBFS(Graph*G,inti){ G->visit[i]=1; qList、push(i); Bfs_part(G); //恢復 makeVisitNull(G); cout<<endl;}Graph*G=newGraph;intmain(){ NewNode(G,'1'); NewNode(G,'2'); NewNode(G,'3'); NewNode(G,'4'); NewNode(G,'5'); NewNode(G,'6'); Print(G); SetSucc1(G,'1','2'); SetSucc1(G,'1','4'); SetSucc1(G,'1','6'); SetSucc1(G,'2','3'); SetSucc1(G,'2','4'); SetSucc1(G,'2','5'); SetSucc1(G,'3','5'); SetSucc1(G,'4','6'); SetSucc1(G,'4','5'); Print(G);cout<<"DFS:"<<endl;DFS(G,0);cout<<"BFS:"<<endl;BFS(G,0); return0;}七、基于深度優(yōu)先搜索算法,寫出求無向圖所有連通子圖得算法,并求連通分量。提示:對于無向圖,從任一個頂點出發(fā)進行DFS遍歷,當本次遍歷完成后,其所訪問得結(jié)點構(gòu)成一個連通子圖;如果還存在沒有訪問過得結(jié)點,則從中任一個結(jié)點出發(fā)進行DFS遍歷,……,直到所有結(jié)點都被訪問。每一次調(diào)用DFS后都得到此非連通圖得一個連通子圖,調(diào)用DFS得次數(shù)就就是連通子圖得個數(shù)。八、網(wǎng)絡(luò)G得鄰接矩陣如下,試畫出該圖,并畫出它得一棵最小生成樹。解:下圖就是一個無向帶權(quán)圖,請給出該圖得鄰接矩陣,并分別按Prim算法與Kruskal算法求最小生成樹(包括算法代碼與畫圖)。代碼:#include<iostream>#include<vector>#include<queue>#include<algorithm>usingnamespacestd;#defineINFINITE0xFFFFFFFF#defineVertexDataunsignedint//頂點數(shù)據(jù)#defineUINTunsignedint#definevexCounts6//頂點數(shù)量charvextex[]={'A','B','C','D','E','F'};structnode{ VertexDatadata; unsignedintlowestcost;}closedge[vexCounts];//Prim算法中得輔助信息typedefstruct{ VertexDatau; VertexDatav; unsignedintcost;//邊得代價}Arc;//原始圖得邊信息voidAdjMatrix(unsignedintadjMat[][vexCounts]){//鄰接矩陣表示法 for(inti=0;i<vexCounts;i++)//初始化鄰接矩陣 for(intj=0;j<vexCounts;j++){ adjMat[i][j]=INFINITE; }}intMinmum(structnode*closedge){//返回最小代價邊 unsignedintmin=INFINITE; intindex=-1; for(inti=0;i<vexCounts;i++){ if(closedge[i]、lowestcost<min&&closedge[i]、lowestcost!=0){ min=closedge[i]、lowestcost; index=i; } } returnindex;}voidMiniSpanTree_Prim(unsignedintadjMat[][vexCounts],VertexDatas){ for(inti=0;i<vexCounts;i++){ closedge[i]、lowestcost=INFINITE; } closedge[s]、data=s;//從頂點s開始 closedge[s]、lowestcost=0; for(inti=0;i<vexCounts;i++){//初始化輔助數(shù)組 if(i!=s){ closedge[i]、data=s; closedge[i]、lowestcost=adjMat[s][i]; } } for(inte=1;e<=vexCounts-1;e++){//n-1條邊時退出 intk=Minmum(closedge);//選擇最小代價邊 cout<<vextex[closedge[k]、data]<<"--"<<vextex[k]<<endl;//加入到最小生成樹 closedge[k]、lowestcost=0;//代價置為0 for(inti=0;i<vexCounts;i++){//更新v中頂點最小代價邊信息 if(adjMat[k][i]<closedge[i]、lowestcost){ closedge[i]、data=k; closedge[i]、lowestcost=adjMat[k][i]; } } }}voidReadArc(unsignedintadjMat[][vexCounts],vector<Arc>&vertexArc){//保存圖得邊代價信息 Arc*temp=NULL; for(unsignedinti=0;i<vexCounts;i++){ for(unsignedintj=0;j<i;j++){ if(adjMat[i][j]!=INFINITE){ temp=newArc; temp->u=i; temp->v=j; temp->cost=adjMat[i][j]; vertexArc、push_back(*temp); } } }}boolpare(ArcA,ArcB){ returnA、cost<B、cost?true:false;}boolFindTree(VertexDatau,VertexDatav,vector<vector<VertexData>>&Tree){ unsignedintindex_u=INFINITE; unsignedintindex_v=INFINITE; for(unsignedinti=0;i<Tree、size();i++){//檢查u,v分別屬于哪顆樹 if(find(Tree[i]、begin(),Tree[i]、end(),u)!=Tree[i]、end()) index_u=i; if(find(Tree[i]、begin(),Tree[i