C++數(shù)據(jù)結(jié)構(gòu)上機(jī)作業(yè)DS作業(yè)和實(shí)驗(yàn)參考答案總匯

2013級(jí)DS作業(yè)和實(shí)驗(yàn)參考答案總匯目錄20141217第一次作業(yè)：復(fù)習(xí)C++9000，9002第二次作業(yè)：順序表插入和刪除操作9003，9004第三次作業(yè)：順序表查找操作和單鏈表建立9012，9006第四次作業(yè)：單鏈表操作9014，9016，9017第五次作業(yè)：特殊線性表?xiàng)２僮?045，9042，9041第六次作業(yè)：特殊線性表隊(duì)列操作9038，9040第七次作業(yè)：二叉樹的順序存儲(chǔ)9050第八次作業(yè)：復(fù)制二叉樹9063第九次作業(yè)：二叉樹的高度寬度9057，9067第十次作業(yè)：圖的鄰接矩陣及遍歷9070，9072，9087第十一次作業(yè)：圖的生成樹9076，9077，9088第十二次作業(yè)：圖的最短路徑9092，9091，9085?。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。?！第一次實(shí)驗(yàn)：順序表9010，9005第二次實(shí)驗(yàn)：順序表29097第三次實(shí)驗(yàn)：單鏈表9007第四次實(shí)驗(yàn)：循環(huán)鏈表9008第五次實(shí)驗(yàn)：遞歸9039第六次實(shí)驗(yàn)：二叉樹的建立及遍歷9019第七次實(shí)驗(yàn)：二叉樹的結(jié)點(diǎn)9054，9056第八次實(shí)驗(yàn)：二叉樹的存儲(chǔ)轉(zhuǎn)換9049第九次實(shí)驗(yàn)：哈夫曼編碼9068第十次實(shí)驗(yàn)：圖的鄰接表及度9071，9079第十一次實(shí)驗(yàn)：圖的存儲(chǔ)轉(zhuǎn)換9089，9084，9083第十二次實(shí)驗(yàn)：模擬考試?。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。〉谝淮巫鳂I(yè)：復(fù)習(xí)C++9000，90029000:矩形面積

ProblemDescription聲明一個(gè)名為rect的矩形類，其屬性為矩形的左下角和右上角兩個(gè)點(diǎn)的x和y坐標(biāo)，該類有效矩形只存在于直角坐標(biāo)系的第一象限內(nèi)。若所構(gòu)成的矩形有效，則計(jì)算矩形的面積；若所構(gòu)成的矩形無效，則輸出“dataerror”。

Input輸入的第一行為一個(gè)數(shù)字n，表示下面有n組數(shù)據(jù)，每組數(shù)據(jù)包括2行；每組數(shù)據(jù)中的第一行表示矩形左下角點(diǎn)的x和y坐標(biāo)，第二行表示矩形右上角點(diǎn)的x和y坐標(biāo)。

Output若所構(gòu)成的矩形有效，則計(jì)算矩形的面積；若所構(gòu)成的矩形無效，則輸出“dataerror”。

SampleInput222441234

SampleOutput44//9000ANSWERCODE1#include<iostream>usingnamespacestd;classrect{public: rect(inta,intb,intc,intd); ~rect(){} intarea();private: intx1,y1,x2,y2;};rect::rect(inta,intb,intc,intd){x1=a;y1=b;x2=c;y2=d;}intrect::area(){return(x2-x1)*(y2-y1);}intmain(){inta,b,c,d,n;cin>>n;while(n--){cin>>a>>b>>c>>d;if(a<0||b<0||c<0||d<0||a>=c||b>=d)cout<<"dataerror"<<endl;else{rectr(a,b,c,d); cout<<r.area()<<endl;}}return0;}9002:數(shù)組的循環(huán)移位

ProblemDescription對(duì)于一個(gè)給定的字符型數(shù)組循環(huán)左移i位，要求盡量不申請(qǐng)空間，實(shí)現(xiàn)“原地”操作。

Input輸入的第一行為一個(gè)數(shù)字n,代表接下來有n組數(shù)據(jù)，每組數(shù)據(jù)包括2行；每組數(shù)據(jù)中的第一行為一個(gè)字符串（長度不超過50），第二行為一個(gè)數(shù)字m，代表要左移的位數(shù)。

Output循環(huán)左移后的字符型數(shù)組內(nèi)容。

SampleInput1abcdefgh3

SampleOutputdefghabc//9002ANSWERCODE1#include<iostream>usingnamespacestd;#defineN20voidReverse(chara[],intfrom,intto){ inti,j;chart;i=from;j=to; while(i<j) {t=a[i];a[i]=a[j];a[j]=t;i++;j--;}}voidConverse(chara[],intn,inti){ Reverse(a,0,i-1);Reverse(a,i,n-1);Reverse(a,0,n-1);}intmain(){ chara[N];intm,n,i;cin>>m; while(m--){ cin>>a>>i; n=strlen(a);i=i%n; Converse(a,n,i); cout<<a<<endl; }return0;}第二次作業(yè)：順序表插入和刪除操作9003，90049003:合并順序表

ProblemDescription假設(shè)有兩個(gè)由小到大有序的有序順序表A和B，現(xiàn)要求將表B并入表A中，且A表仍保持由小到大的有序性。若合并后的順序表表長超過總?cè)萘?0，則輸出“notenough”。

Input第一行為一個(gè)數(shù)字n,表示下面有n組數(shù)據(jù)，每組數(shù)據(jù)包括4行；每組數(shù)據(jù)中的第一行表示表A的表長，第二行表示表A的數(shù)據(jù)元素，第三行表示表B的表長，第四行表示表B的數(shù)據(jù)元素。

Output若合并成功，輸出兩行信息，第一行表示合并后A表的表長，第二行表示合并后A表的數(shù)據(jù)元素，元素之間用一個(gè)空格分隔；若合并后的順序表表長超過總?cè)萘?0，則輸出“notenough”。

SampleInput1413817361015

SampleOutput71368101517//9003ANSWERCODE1#include<iostream>usingnamespacestd;constintMaxSize=20;//有兩個(gè)由小到大有序的有序順序表A和Bvoidcombine(intA[],intA_len,intB[],intB_len){ if((A_len+B_len)>MaxSize) cout<<"notenough\n"; else { inti=0,j=0,k=0; for(i=0;i<B_len;i++) { while(B[i]>A[j])//找到B[i]在A表中的插入位置j {j++;} for(k=A_len-1;k>=j;k--)//把j(包括j)后的元素往后挪一個(gè)位置，空出j來。 {A[k+1]=A[k];} A[j]=B[i];//把B[i]插入A表中的位置j A_len++;//A表長度加1 } cout<<A_len<<endl; for(i=0;i<(A_len-1);i++) cout<<A[i]<<""; cout<<A[i]<<endl; }}voidmain(){ intA[MaxSize],B[MaxSize],A_len,B_len,n,i; cin>>n; while(n--){ cin>>A_len; for(i=0;i<A_len;i++){cin>>A[i];} cin>>B_len; for(i=0;i<B_len;i++){cin>>B[i];} combine(A,A_len,B,B_len); } }9004:連續(xù)刪除

ProblemDescription從由小到大有序的順序表中刪除其值在[s,t]之間（含s和t）的所有元素，且不改變順序表的有序性。如果s>=t則顯示“dataerror”；否則輸出順序表的表長和順序表中的元素，若處理后的順序表為空，則不輸出任何信息。

Input輸入的第一行為一個(gè)數(shù)字n，表示下面有n組數(shù)據(jù)，每組數(shù)據(jù)包括3行；每組數(shù)據(jù)中的第一行包含兩個(gè)數(shù)字s和t，第二行為順序表的表長len（0<len<=20），第三行為順序表的數(shù)據(jù)元素。

Output對(duì)于每組數(shù)據(jù)，如果s>=t，則直接輸出“dataerror”，否則輸出兩行信息：第一行為處理后順序表的表長，第二行為處理后順序表中的元素，元素之間用一個(gè)空格分隔，如果處理后的順序表為空，則不輸出任何信息。

SampleInput1818713510171925

SampleOutput51351925//9004ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,s,t,len,A[21],i,s_i,t_i,j,span; cin>>n; while(n--){ cin>>s>>t>>len; for(i=0;i<len;i++)cin>>A[i]; if(s>=t||len<=0||len>20) {cout<<"dataerror"<<endl;continue;} s_i=0;t_i=len-1; while(A[s_i]<s&&s_i<len)s_i++; while(A[t_i]>t&&t_i>=0)t_i--; if(s_i<=t_i) { span=t_i-s_i+1; for(j=s_i;j<len;j++)A[j]=A[j+span]; len-=span; } if(len!=0) { cout<<len<<endl; for(i=0;i<len-1;i++)cout<<A[i]<<""; cout<<A[i]<<endl; } } return0;}第三次作業(yè)：順序表查找操作和單鏈表建立9012，90069012:找唯一數(shù)

ProblemDescription在一個(gè)表長為n的順序表中，除一個(gè)元素之外，其余的元素都出現(xiàn)了兩次。請(qǐng)找出這個(gè)僅出現(xiàn)一次的元素。

Input有多組數(shù)據(jù)，每組第一行表示表長n（1<=n<=11111）；第二行表示順序表的各元素。

Output輸出這個(gè)唯一數(shù)。

SampleInput52213172113-123

SampleOutput3-1//9012ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,i,j,A[11112],B[11112]; while(cin>>n) { if(n>=1&&n<=11111) { for(i=0;i<n;i++)cin>>A[i]; for(i=0;i<n;i++)B[i]=1; for(i=0;i<n;i++) { for(j=i+1;j<n;j++) {if(A[i]==A[j]){B[i]=0;B[j]=0;break;}} } for(i=0;i<n;i++) {if(B[i]==1)cout<<A[i]<<endl;} } } return0;}9006:單鏈表的建立和遍歷

ProblemDescription輸入N個(gè)整數(shù)，按照輸入的順序建立單鏈表存儲(chǔ)，并遍歷所建立的單鏈表，輸出這些數(shù)據(jù)。

Input輸入數(shù)據(jù)有多組，每組數(shù)據(jù)占兩行；每組第一行為一個(gè)數(shù)字N（N<=50）；第二行有N個(gè)整數(shù)。

Output輸出這組整數(shù)，數(shù)字之間用一個(gè)空格分隔。

SampleInput51232457854

SampleOutput1232457854//9006ANSWERCODE1#include<iostream>usingnamespacestd;structNode{intdata;Node*next;};intmain(){ intN,i,A[51]; Node*head=newNode,*p,*tail; while(cin>>N) { if(N>0) { for(i=0;i<N;i++)cin>>A[i]; tail=head; for(i=0;i<N;i++) { p=newNode; p->data=A[i]; tail->next=p; tail=p; } tail->next=NULL;p=head->next; for(i=0;i<N-1;i++) { cout<<p->data<<"";p=p->next;} cout<<p->data<<endl; } } return0;}第四次作業(yè)：單鏈表操作9014，9016，90179014:刪最小值

ProblemDescription設(shè)有一單鏈表，現(xiàn)要求刪除其最小值（假設(shè)最小值唯一）。若刪除成功，則輸出被刪的最小值；若刪除失敗，則輸出“notexist”。

Input有多組數(shù)據(jù)，每組第一行為單鏈表的元素個(gè)數(shù)n（0<=n<100）；第二行為單鏈表的各個(gè)元素。

Output若刪除成功，則輸出被刪的最小值；若刪除失敗，則輸出“notexist”。

SampleInput8426-319145524167

SampleOutput-31//9014ANSWERCODE1#include<iostream>usingnamespacestd;structNode{intdata;Node*next;};intmain(){ inti,n,data[100],min; Node*first,*p,*q,*s,*tail; while(cin>>n) { if(n==0){cout<<"notexist\n";continue;} for(i=0;i<n;i++)cin>>data[i]; first=newNode; first->next=NULL;tail=first; for(i=0;i<n;i++) {s=newNode;s->data=data[i];tail->next=s;tail=s;} tail->next=NULL; p=first;min=first->next->data; while(p->next) { q=p;p=p->next; if(p->data<min)min=p->data; } p=first->next;q=first; while(p) {if(p->data==min)break; else{q=p;p=p->next;}} if(p&&q){q->next=p->next;deletep;cout<<min<<endl;} else{cout<<"notexist\n";} } return0;}9016:查找倒數(shù)第k個(gè)結(jié)點(diǎn)

ProblemDescription有一單鏈L，請(qǐng)輸出該單鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)的值。若該結(jié)點(diǎn)不存在，則輸出“notfind”。

Input有多組數(shù)據(jù)，每組第一行為單鏈表元素個(gè)數(shù)n和k值（0<n<100，k>0）；第二行為單鏈表的各元素。

Output輸出該單鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)的值。若該結(jié)點(diǎn)不存在，則輸出“notfind”。

SampleInput51123455512345

SampleOutput51//9016ANSWERCODE1#include<iostream>usingnamespacestd;structNode{intdate; Node*next;};intmain(){ intn,k,i,c,data[100];Node*first,*r,*p,*s; while(cin>>n>>k) { for(i=0;i<n;i++)cin>>data[i]; first=newNode; r=first; for(i=0;i<n;i++) { s=newNode;s->date=data[i]; r->next=s;r=s; } r->next=NULL; //倒數(shù)第k個(gè)就是正數(shù)第n-k+1個(gè)。 if(k<=n&&k>=1) { p=first->next;c=1; while(p&&c<(n-k+1)){p=p->next;c++;} if(p&&c==(n-k+1)){cout<<p->date<<endl;} } elsecout<<"notfind"<<endl; } return0;}9017:統(tǒng)計(jì)選票

ProblemDescription設(shè)有m個(gè)候選人n張選票，每張選票選且只選一人，候選人編號(hào)依次為1，2，3，...，m?，F(xiàn)將這n張選票存于一單鏈表中，要求統(tǒng)計(jì)并輸出每個(gè)候選人的得票結(jié)果。

Input有多組數(shù)據(jù)，每組第一行為候選人總數(shù)m和選票總數(shù)n（m>0，0<n<100）；第二行為n張選票的內(nèi)容。

Output輸出每個(gè)候選人的得票結(jié)果，數(shù)字之間用一個(gè)空格隔開。

SampleInput361312215833433211

SampleOutput32121410//9017ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intvotes[100],n,i,m,c; while(cin>>m>>n) { for(i=1;i<=m;i++)votes[i]=0; for(i=0;i<n;i++) { cin>>c; votes[c]++; } for(i=1;i<m;i++)cout<<votes[i]<<""; cout<<votes[m]<<endl; } return0;}第五次作業(yè)：特殊線性表?xiàng)２僮?045，9042，90419045:判棧輸出序列的有效性

ProblemDescription設(shè)一個(gè)棧的輸入序列為1,2,3,...,n-1,n。請(qǐng)編寫一個(gè)算法，判斷一個(gè)序列p1,p2,p3,...,pn是否是一個(gè)有效的棧輸出序列。若有效輸出1，無效輸出0。

Input有多組數(shù)據(jù)，每組第一行為序列長度n（n<=50），第二行為一個(gè)由1~n值組成的長度為n且值無重復(fù)的序列。

Output棧輸出序列有效輸出1，無效輸出0。

SampleInput31233312

SampleOutput10//9045ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,i,j,in,out;//in輸入序列指針，out輸出序列指針 intoutput[51],stack[51],top=-1; while(cin>>n) { for(i=0;i<n;i++)cin>>output[i]; top=-1;in=0; for(i=0;i<n;i++){ out=output[i]; if(out>in){ for(j=in+1;j<=out;j++)stack[++top]=j; in=out; } if(stack[top]==output[i])top--; else{cout<<"0\n";break;} } if(i==n&&top==-1)cout<<"1\n"; } return0;}9042:判操作序列有效性

ProblemDescription假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則成為非法序列。請(qǐng)編寫一個(gè)對(duì)該操作序列的有效性進(jìn)行判斷，若有效輸出1，無效輸出0。

Input有多組數(shù)據(jù)，每組為由I和O組成的序列，序列長度不超過50。

Output操作序列有效輸出1，無效輸出0。

SampleInputIOIIOIOOIOOIOIIO

SampleOutput10//9042ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,i,flag; charstr[51],stack[51],top=-1; while(cin>>str) { n=strlen(str);top=-1;flag=0; for(i=0;i<n;i++) { if(str[i]=='I'){stack[++top]=str[i];} elseif(str[i]=='O') { if(top>-1)top--; else{cout<<"0\n";flag=1;break;} } else{cout<<"0\n";flag=1;break;} } if(top==-1&&i==n&&flag==0){cout<<"1\n";} else{if(flag==0)cout<<"0\n";} } return0;}9041:判括號(hào)匹配

ProblemDescription任意輸入一個(gè)由若干個(gè)圓括號(hào)、方括號(hào)和花括號(hào)組成的字符串，設(shè)計(jì)一個(gè)算法判斷該串中的括號(hào)是否配對(duì)。

Input有多組數(shù)據(jù)，每組為一個(gè)包含3類括號(hào)的字符串，串長不超過100。

Output若該串中的括號(hào)匹配輸出1，否則輸出0。

SampleInput([{}])([{}})([{)]}

SampleOutput100//9041ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ inti,len,flag; charstr[100],stack[100],top=-1; while(cin>>str) { len=strlen(str);flag=0;top=-1; for(i=0;i<len;i++) { if(str[i]=='('||str[i]=='['||str[i]=='{'){stack[++top]=str[i];} elseif((str[i]==')')&&(stack[top]=='(')||(str[i]==']')&&(stack[top]=='[')||(str[i]=='}')&&(stack[top]=='{')){top--;} else{cout<<"0\n";flag=1;break;} } if(top==-1&&i==len&&flag==0){cout<<"1\n";} else{if(flag==0)cout<<"0\n";} } return0;}第六次作業(yè)：特殊線性表隊(duì)列操作9038，90409038:循環(huán)隊(duì)列的操作

ProblemDescription現(xiàn)有一長度為n的整數(shù)序列和一最大容量為m的循環(huán)隊(duì)列（用長為m+1的一維數(shù)組實(shí)現(xiàn)），要求將該序列中的偶數(shù)存入循環(huán)隊(duì)列中；當(dāng)循環(huán)隊(duì)列滿時(shí)，將循環(huán)隊(duì)列中的所有元素全部出隊(duì)，并按存入的先后順序在同一行內(nèi)依次輸出，即每行輸出m個(gè)元素，每個(gè)元素后輸出一個(gè)空格。

Input有多組數(shù)據(jù)，每組第一行為整數(shù)序列的個(gè)數(shù)n和循環(huán)隊(duì)列的最大容量m（m<=n<=100，0<m<10）；第二行為整數(shù)序列的各個(gè)元素。

Output有多行數(shù)據(jù)，先輸出對(duì)應(yīng)行號(hào)，每行輸出m個(gè)元素，均為偶數(shù)，每個(gè)元素后輸出一個(gè)空格。

SampleInput10491027168124311039102716812134

SampleOutput1:1021681:102162:8124//9038ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ inti,j,c,l,n,m,A[101],Queue[101],front,rear; while(cin>>n>>m) { for(i=0;i<n;i++)cin>>A[i]; front=rear=0;c=0;l=0; for(i=0;i<n;i++) { if(c<m&&A[i]%2==0) { c++; rear=(rear+1)%(m+1); Queue[rear]=A[i]; } if(c==m) { cout<<++l<<":"; for(j=front+1;j<=rear;j++)cout<<Queue[j]<<""; cout<<endl; c=0;front=rear=0; } } } return0;}9040:火車車廂重排

ProblemDescription一列貨運(yùn)列車共有n節(jié)車廂，每節(jié)車廂將停放在不同的車站。假定n個(gè)車站的編號(hào)分別為1~n，即貨運(yùn)列車按照第n站至第1站的次序經(jīng)過這些車站。為了便于從列車上卸掉相應(yīng)的車廂，車廂的編號(hào)應(yīng)與車站的編號(hào)相同。這樣，在每個(gè)車站只需卸掉最后一節(jié)車廂。因此，對(duì)于給定的任意次序車廂，必須進(jìn)行重新排列，使其符合要求。車廂重排工作可通過轉(zhuǎn)軌站完成，在轉(zhuǎn)軌站中有一個(gè)入軌、一個(gè)出軌和k個(gè)緩沖軌，緩沖軌位于入軌和出軌之間。假定緩沖軌按先進(jìn)先出的方式工作，現(xiàn)要求設(shè)計(jì)算法解決火車車廂重排問題。

Input有多組數(shù)據(jù)，每組第一行為車廂節(jié)數(shù)n和緩沖軌數(shù)目k（2<=k<=5，k<=n<=10），第二行為初始給定的車廂編號(hào)次序序列。

Output若給定的車廂編號(hào)次序序列可重排，則輸出1；否則輸出0。

SampleInput9336924718593369247581

SampleOutput10//9040ANSWERCODE1#include<iostream>#include<queue>usingnamespacestd;intmain(){ intn,k,carNum[11],i,j,rearrange; while(cin>>n>>k) { for(i=0;i<n;i++)cin>>carNum[i]; queue<int>Q[5];rearrange=1; for(i=0;i<n;i++) { for(j=0;j<k;j++) { if(Q[j].empty()||carNum[i]>Q[j].back()) {Q[j].push(carNum[i]);break;} } if(j==k) {rearrange=0;break;} } cout<<rearrange<<endl; } return0;}第七次作業(yè)：二叉樹的順序存儲(chǔ)90509050:順序存儲(chǔ)的前序遍歷

ProblemDescription給你一個(gè)采用順序存儲(chǔ)結(jié)構(gòu)的二叉樹，請(qǐng)你設(shè)計(jì)一個(gè)算法求出它的前序遍歷。

Input輸入數(shù)據(jù)有多組，每組的第一行為一個(gè)正數(shù)n,表示該二叉樹的節(jié)點(diǎn)個(gè)數(shù)。

接下來有n個(gè)字符，表示各個(gè)位置上的元素，當(dāng)字符為'#'時(shí)表示當(dāng)前節(jié)點(diǎn)為空。

Output輸出該二叉樹的前序遍歷

SampleInput6ABCDEF6ABC#DE

SampleOutputABDECFABDCE//9050ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,i,top,S[100];charch[100]; while(cin>>n) { cin>>ch; if(ch[0]=='#')continue; top=-1;i=0; while(top!=-1||i<n) { while(i<n){if(ch[i]!='#')cout<<ch[i];S[++top]=i;i=2*i+1;} if(top!=-1){i=S[top--];i=2*i+2;} } cout<<endl; } return0;}//9050ANSWERCODE2#include<iostream>usingnamespacestd;charchLeverData[101];voidpreorder(inti,intn){ if(chLeverData[i]=='#'||i>=n)return; cout<<chLeverData[i]; preorder(2*i+1,n); preorder(2*i+2,n);}voidmain(){ intn; while(cin>>n) { cin>>chLeverData; preorder(0,n); cout<<endl; }}第八次作業(yè)：復(fù)制二叉樹90639063:復(fù)制二叉樹

ProblemDescription設(shè)有一棵二叉樹，其節(jié)點(diǎn)值為字符型并假設(shè)各值互不相等，采用二叉鏈表存儲(chǔ)表示?，F(xiàn)輸入其擴(kuò)展二叉樹的前序遍歷序列，要求復(fù)制該二叉樹，并對(duì)復(fù)制得來的二叉樹進(jìn)行中序遍歷。

Input第一行為一個(gè)整數(shù)n，表示以下有n組測試數(shù)據(jù)，每組測試數(shù)據(jù)占一行，為擴(kuò)展二叉樹的前序遍歷序列。

Output輸出復(fù)制完的新二叉樹的中序遍歷序列，空二叉樹則不輸出任何信息。

SampleInput2AB#D##C##ABD##E##C#F##

SampleOutputBDACDBEACF//9063ANSWERCODE1#include<iostream>usingnamespacestd;structBinode{ chardata;Binode*lchild,*rchild;};Binode*Great(){ Binode*bt;charch; cin>>ch; if(ch=='#')bt=NULL; else { bt=newBinode; bt->data=ch; bt->lchild=Great(); bt->rchild=Great(); } returnbt;}Binode*copy(Binode*bt){ Binode*bt1; if(bt==NULL) returnNULL; else { bt1=newBinode; bt1->data=bt->data; bt1->lchild=copy(bt->lchild); bt1->rchild=copy(bt->rchild); } returnbt1;}voidInorder(Binode*bt1){ if(bt1==NULL) return; else { Inorder(bt1->lchild); cout<<bt1->data; Inorder(bt1->rchild); } };intmain(){ intn; cin>>n; while(n--) { Binode*bt=Great(); Binode*bt1=copy(bt); Inorder(bt1); if(bt1!=NULL) cout<<endl; } return0;}//9063ANSWERCODE2#include<iostream>usingnamespacestd;structBiNode{chardata;BiNode*lchild,*rchild;};BiNode*Creat(){ BiNode*bt;charch; cin>>ch; if(ch=='#')bt=NULL; else { bt=newBiNode; bt->data=ch; bt->lchild=Creat(); bt->rchild=Creat(); } returnbt;}voidInOrder(BiNode*root){if(root==NULL)return;//遞歸調(diào)用的結(jié)束條件 else{ InOrder(root->lchild);//中序遞歸遍歷root的左子樹 cout<<root->data;InOrder(root->rchild);//中序遞歸遍歷root的右子樹 }}//層序遍歷復(fù)制二叉樹BiNode*copy_bitree(BiNode*root){ intfront=-1,rear=-1,newfront=-1,newrear=-1; BiNode*Q[100],*newQ[100],*oldp,*newp,*newroot; if(root==NULL)returnNULL;//空二叉樹 oldp=root; newp=newBiNode; newp->data=oldp->data; newroot=newp;//新二叉樹的根指針 Q[++rear]=oldp;//入隊(duì) newQ[++newrear]=newp;//入隊(duì) while(rear!=front) { oldp=Q[++front];//出隊(duì) newp=newQ[++newfront];//出隊(duì) if(oldp->lchild==NULL)newp->lchild=NULL; else { newp->lchild=newBiNode; newp->lchild->data=oldp->lchild->data; Q[++rear]=oldp->lchild; newQ[++newrear]=newp->lchild; } if(oldp->rchild==NULL)newp->rchild=NULL; else { newp->rchild=newBiNode; newp->rchild->data=oldp->rchild->data; Q[++rear]=oldp->rchild; newQ[++newrear]=newp->rchild; } } returnnewroot;}voidmain(){ intn; BiNode*root,*newroot; cin>>n; while(n--) { root=Creat(); newroot=copy_bitree(root); if(newroot==NULL) continue; InOrder(newroot);//中序遍歷新二叉樹 cout<<endl; }}第九次作業(yè)：二叉樹的高度寬度9057，90679057:Tree'sDepth

ProblemDescription一個(gè)名字叫SmallGreen的同學(xué)，很喜歡研究樹的問題。某一天，他隨意地在紙上亂涂亂畫，畫出了各不相同的二叉樹，他同時(shí)在想：一顆滿的二叉樹的深度并不難求。但如果要求出一顆二叉樹（可能不是滿二叉樹）的深度，那么該如何求呢？

Input輸入包含多個(gè)例子，每個(gè)例子的第一行為一個(gè)整數(shù)n，表示以下有n組數(shù)據(jù)，每組數(shù)據(jù)占一行，為擴(kuò)展二叉樹的前序遍歷序列（長度小于50，若節(jié)點(diǎn)為NULL則用'#'表示，否則用小寫字母表示）。

Output輸出該二叉樹的深度。

SampleInput2abcd####efg####abcd####efg#h###i##

SampleOutput45//9057ANSWERCODE1#include<iostream>usingnamespacestd;structBiNode{chardata;BiNode*lchild,*rchild;};BiNode*Creat(){ BiNode*p; charch; cin>>ch; if(ch=='#') returnNULL; else { p=newBiNode; p->data=ch; p->lchild=Creat(); p->rchild=Creat(); } returnp;}intDepth(BiNode*bt){ intl,r; if(bt==NULL)return0; else { l=Depth(bt->lchild); r=Depth(bt->rchild); return(l>=r)?(l+1):(r+1); }}main(){ intn; while(cin>>n) { while(n--) { BiNode*p=Creat(); cout<<Depth(p)<<endl; } } return0;}//9057ANSWERCODE2#include<iostream>usingnamespacestd;structBiNode{chardata;BiNode*lchild,*rchild;};intdeep;BiNode*Creat(inti){ BiNode*p; charch; cin>>ch; if(ch=='#') returnNULL; else{ p=newBiNode; p->data=ch; if(deep<i)deep=i; p->lchild=Creat(i+1); p->rchild=Creat(i+1); } returnp;}intmain(){ intn; while(cin>>n) { while(n--) { deep=0; BiNode*root=Creat(1); cout<<deep<<endl; } } return0;}9067:二叉樹的寬度

ProblemDescription二叉樹的寬度是指二叉樹各層結(jié)點(diǎn)數(shù)的最大值。設(shè)有一棵二叉樹，其節(jié)點(diǎn)值為字符型并假設(shè)各值互不相等，采用二叉鏈表存儲(chǔ)表示。設(shè)計(jì)一個(gè)算法，輸出該二叉樹的寬度?？斩鏄涞膶挾葹?。

Input第一行為一個(gè)整數(shù)n，表示以下有n組數(shù)據(jù)，每組數(shù)據(jù)占一行，為擴(kuò)展二叉樹的前序遍歷序列。

Output輸出該二叉樹的寬度。

SampleInput3AB#D##C##ABD##E##C#F##HDA##C#B##GF#E###

SampleOutput233//9067ANSWERCODE1#include<iostream>usingnamespacestd;structBiNode{chardata;BiNode*lchild,*rchild,*parent;intlevel;BiNode(){parent=NULL;level=1;}};classBiTree{public: BiTree(){root=Creat(); } ~BiTree(){Release(root);} voidPreOrder(){PreOrder(root);} private: BiNode*root; BiNode*Creat(); voidPreOrder(BiNode*root); voidRelease(BiNode*root); };intW[51];intmain(){ intn,i,max;cin>>n; while(n--){ max=0; for(i=0;i<51;i++)W[i]=0; BiTreebt; bt.PreOrder(); for(i=0;i<51;i++){if(W[i]>max)max=W[i];} cout<<max<<endl; } return0;}BiNode*BiTree::Creat(){ charch;BiNode*p; cin>>ch; if(ch=='#')p=NULL; else{ p=newBiNode;p->data=ch; p->lchild=Creat();if(p->lchild){p->lchild->parent=p;} p->rchild=Creat();if(p->rchild){p->rchild->parent=p;} } returnp;}voidBiTree::PreOrder(BiNode*root){ if(root==NULL)return; else{ if(root->parent)root->level=root->parent->level+1; W[root->level]=W[root->level]+1; PreOrder(root->lchild); PreOrder(root->rchild); }}voidBiTree::Release(BiNode*root){ if(root!=NULL) { Release(root->lchild); Release(root->rchild); deleteroot; }}//9067ANSWERCODE2#include<iostream>usingnamespacestd;intsum[100];structBiNode{chardata;BiNode*lchild,*rchild;};BiNode*Creat(inti){ BiNode*p;charch; cin>>ch; if(ch=='#') returnNULL; else { p=newBiNode; p->data=ch; sum[i]++; p->lchild=Creat(i+1); p->rchild=Creat(i+1); } returnp;}intmain(){ intn,i,width;BiNode*root; while(cin>>n) { while(n--) { memset(sum,0,sizeof(sum)); root=Creat(1); width=0; for(i=1;i<100;i++) if(width<sum[i])width=sum[i]; cout<<width<<endl; } } return0;}第十次作業(yè)：圖的鄰接矩陣及遍歷9070，9072，90879070:求度最大的頂點(diǎn)編號(hào)

ProblemDescription設(shè)有一無向圖G，采用鄰接矩陣存儲(chǔ)，現(xiàn)要求設(shè)計(jì)一個(gè)函數(shù)，用于求圖中度數(shù)最大的頂點(diǎn)，并輸出其對(duì)應(yīng)的存儲(chǔ)編號(hào)（下標(biāo)）。（注：度數(shù)最大的頂點(diǎn)可能有多個(gè)）

Input有多組測試數(shù)據(jù)，每組數(shù)據(jù)的第一行表示圖的頂點(diǎn)數(shù)n和圖的邊數(shù)e（0<n<20），第二行表示各頂點(diǎn)的值，按輸入順序進(jìn)行存儲(chǔ)，后面有e行，每一行表示每條邊所依附的頂點(diǎn)的存儲(chǔ)編號(hào)（下標(biāo)），兩個(gè)下標(biāo)之間用空格隔開。

Output度數(shù)最大的頂點(diǎn)對(duì)應(yīng)的存儲(chǔ)編號(hào)（下標(biāo)），各下標(biāo)之間用空格隔開。

SampleInput44ABCD01031213

SampleOutput1//9070ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,e,i,j,degree[20],max,maxi;charV[20]; while(cin>>n>>e>>V) { for(i=0;i<n;i++)degree[i]=0; for(intk=0;k<e;k++) {cin>>i>>j;degree[i]++;degree[j]++;} max=degree[0];maxi=0; for(i=0;i<n;i++) {if(degree[i]>=max){max=degree[i];maxi=i;} } for(i=0;i<n;i++) {if(degree[i]==max&&i!=maxi)cout<<i<<""; } cout<<maxi<<endl; } return0;}//9070ANSWERCODE2#include<iostream>usingnamespacestd;intmain(){ intn,e,i,j,k,Max,f,degree[20],arc[20][20]; charVex[20]; while(cin>>n>>e>>Vex) { for(i=0;i<n;i++) {for(j=0;j<n;j++)arc[i][j]=0;} for(k=0;k<e;k++) {cin>>i>>j;arc[i][j]=1;arc[j][i]=1;} Max=0; for(i=0;i<n;i++) { degree[i]=0; for(j=0;j<n;j++){if(arc[i][j]==1)degree[i]++;} if(degree[i]>Max)Max=degree[i]; } f=0; for(i=0;i<n;i++) { if(degree[i]==Max) {if(f==0)cout<<i;elsecout<<""<<i; f=1;} } cout<<endl; } return0;}9072:存儲(chǔ)網(wǎng)圖

ProblemDescription設(shè)有一無向網(wǎng)圖，其頂點(diǎn)值為字符型并假設(shè)各值互不相等，采用鄰接矩陣表示法存儲(chǔ)表示。設(shè)計(jì)一個(gè)算法，存儲(chǔ)該網(wǎng)圖并輸出其鄰接矩陣。

Input有多組測試數(shù)據(jù)，每組數(shù)據(jù)的第一行為兩個(gè)整數(shù)n和e，表示n個(gè)頂點(diǎn)和e條邊（0<n<20）；第二行為其n個(gè)頂點(diǎn)的值，按輸入順序進(jìn)行存儲(chǔ)；后面有e行，表示e條邊的信息，每條邊信息占一行，包括邊所依附的頂點(diǎn)下標(biāo)i和j，以及邊上的權(quán)值w（可為負(fù)），設(shè)三者均為整型，數(shù)據(jù)之間用空格隔開。

Output輸出該網(wǎng)圖的鄰接矩陣，每組輸出占n行，每行有n個(gè)數(shù)據(jù)，每兩個(gè)數(shù)據(jù)之間用一個(gè)空格隔開，若無邊用'#'表示。

SampleInput44ABCD014033126138

SampleOutput04#34068#60#38#0//9072ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,e,i,j,k,w,arc[20][20];charVex[20]; while(cin>>n>>e>>Vex) { for(i=0;i<n;i++) {for(j=0;j<n;j++){arc[i][j]=10000;}} for(i=0;i<n;i++)arc[i][i]=0; for(k=0;k<e;k++) { cin>>i>>j>>w; arc[i][j]=w; arc[j][i]=w; } for(i=0;i<n;i++) { for(j=0;j<(n-1);j++) { if(arc[i][j]==10000){cout<<'#'<<"";} elsecout<<arc[i][j]<<""; } if(arc[i][j]==10000){cout<<'#'<<endl;} elsecout<<arc[i][j]<<endl; } } return0;}9087:鄰接矩陣遍歷

ProblemDescription給出一個(gè)無向圖的各個(gè)點(diǎn)之間的鄰接關(guān)系，輸出遍歷序列。

Input有多組數(shù)據(jù)，每組數(shù)據(jù)第一行有兩個(gè)整數(shù)n、m,(0<n,m<100)，n表示是有n個(gè)點(diǎn)（1~n）形成的圖，接下來有m行數(shù)據(jù)，每一行有兩個(gè)整數(shù)（表示點(diǎn)的序號(hào)），說明這兩點(diǎn)之間有一條邊。

Output分別輸出從標(biāo)號(hào)為1點(diǎn)開始深度和廣度優(yōu)先搜索的序列，每個(gè)數(shù)之后有一個(gè)空格。每個(gè)序列分別占一行。

SampleInput89121324253637454867

SampleOutput1245836712345678//9087ANSWERCODE1#include<iostream>usingnamespacestd;intn,visited[100],visited2[100],arc[100][100];voidDFS(intv){ cout<<v<<"";visited[v]=1; for(intj=1;j<=n;j++) {if(arc[v][j]==1&&visited[j]==0)DFS(j);} }voidBFS(intv){ intfront=-1,rear=-1,Q[100]; cout<<v<<"";visited2[v]=1; Q[++rear]=v; while(front!=rear) { v=Q[++front]; for(intj=1;j<=n;j++) if(arc[v][j]==1&&visited2[j]==0) {cout<<j<<"";visited2[j]=1;Q[++rear]=j;} }}voidmain(){ intm,i,j,k; while(cin>>n>>m) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++)arc[i][j]=0;} for(k=0;k<m;k++) {cin>>i>>j;arc[i][j]=arc[j][i]=1;} for(i=1;i<=n;i++) {visited[i]=0;visited2[i]=0;} DFS(1);cout<<endl; BFS(1);cout<<endl; }}第十一次作業(yè)：圖的生成樹9076，9077，90889076:深度優(yōu)先生成樹

ProblemDescription設(shè)有一連通無向圖，其頂點(diǎn)值為字符型并假設(shè)各值互不相等，采用鄰接矩陣表示法存儲(chǔ)表示。利用DFS算法求其深度優(yōu)先生成樹（從下標(biāo)0的頂點(diǎn)開始遍歷），并在遍歷過程中輸出深度優(yōu)先生成樹的每一條邊。

Input有多組測試數(shù)據(jù)，每組數(shù)據(jù)的第一行為兩個(gè)整數(shù)n和e，表示n個(gè)頂點(diǎn)和e條邊（0<n<20）；第二行為其n個(gè)頂點(diǎn)的值，按輸入順序進(jìn)行存儲(chǔ)；后面有e行，表示e條邊的信息，每條邊信息占一行，包括邊所依附的頂點(diǎn)下標(biāo)i和j，數(shù)據(jù)之間用空格隔開。

Output輸出深度優(yōu)先生成樹的每一條邊，每組輸出占一行，每條邊信息之間有一空格，每行最后均有一空格，具體格式見樣例。

SampleInput44ABCD01031213

SampleOutput(A,B)(B,C)(B,D)//9076ANSWERCODE1#include<iostream>usingnamespacestd;intn,visited[100],arc[100][100];charvertex[20];voidDFS_spanningTree(intv){ visited[v]=1; for(intj=0;j<n;j++) { if(arc[v][j]==1&&visited[j]==0) { cout<<"("<<vertex[v]<<","<<vertex[j]<<")"; DFS_spanningTree(j); } } }voidmain(){ inte,i,j,k; while(cin>>n>>e>>vertex) { for(i=0;i<n;i++) { for(j=0;j<n;j++)arc[i][j]=0;} for(k=0;k<e;k++) {cin>>i>>j;arc[i][j]=arc[j][i]=1;} for(i=0;i<n;i++){visited[i]=0;} DFS_spanningTree(0);cout<<endl; }}9077:廣度優(yōu)先生成樹

ProblemDescription設(shè)有一連通無向圖，其頂點(diǎn)值為字符型并假設(shè)各值互不相等，采用鄰接矩陣表示法存儲(chǔ)表示。利用BFS算法求其廣度優(yōu)先生成樹（從下標(biāo)0的頂點(diǎn)開始遍歷），并在遍歷過程中輸出廣度優(yōu)先生成樹的每一條邊。

Input有多組測試數(shù)據(jù)，每組數(shù)據(jù)的第一行為兩個(gè)整數(shù)n和e，表示n個(gè)頂點(diǎn)和e條邊（0<n<20）；第二行為其n個(gè)頂點(diǎn)的值，按輸入順序進(jìn)行存儲(chǔ)；后面有e行，表示e條邊的信息，每條邊信息占一行，包括邊所依附的頂點(diǎn)下標(biāo)i和j，數(shù)據(jù)之間用空格隔開。

Output輸出廣度優(yōu)先生成樹的每一條邊，每組輸出占一行，每條邊信息之間有一空格，每行最后均有一空格，具體格式見樣例。

SampleInput44ABCD01031213

SampleOutput(A,B)(A,D)(B,C)//9077ANSWERCODE1#include<iostream>usingnamespacestd;intn,visited[100],arc[100][100];charvertex[20];voidBFS_spanningTree(intv){ intfront=-1,rear=-1,Q[100];; visited[v]=1;Q[++rear]=v; while(front!=rear) { v=Q[++front]; for(intj=0;j<n;j++) if(arc[v][j]==1&&visited[j]==0){ cout<<"("<<vertex[v]<<","<<vertex[j]<<")"; visited[j]=1;Q[++rear]=j; } }}voidmain(){ inte,i,j,k; while(cin>>n>>e>>vertex) { for(i=0;i<n;i++) { for(j=0;j<n;j++)arc[i][j]=0;} for(k=0;k<e;k++) {cin>>i>>j;arc[i][j]=arc[j][i]=1;} for(i=0;i<n;i++){visited[i]=0;} BFS_spanningTree(0);cout<<endl; }}9088:村村相連

ProblemDescription漳州市政府調(diào)查鄉(xiāng)村交通狀況，得到的統(tǒng)計(jì)表中列出了任意兩村莊間的距離。市政府的目標(biāo)是使全省任何兩個(gè)村莊間都可以實(shí)現(xiàn)公路交通（但不一定有直接的公路相連，只要能間接通過公路可達(dá)即可），并要求鋪設(shè)的公路總長度為最小。請(qǐng)計(jì)算最小的公路總長度。

Input測試輸入包含若干測試用例。每個(gè)測試用例的第1行給出村莊數(shù)目N(N<100)和M；隨后的M行對(duì)應(yīng)村莊間的距離，每行給出一對(duì)正整數(shù)，分別是兩個(gè)村莊的編號(hào)，以及此兩村莊間的距離。為簡單起見，村莊從1到N編號(hào)。

當(dāng)N、M為0時(shí)，輸入結(jié)束，該用例不被處理。

Output對(duì)每個(gè)測試用例，在1行里輸出最小的公路總長度，如果未能找到請(qǐng)輸出"nofound!"。

SampleInput331211322344612113414123324234500

SampleOutput35//9088ANSWERCODE1#include<iostream>usingnamespacestd;intn,arc[100][100];voidPrim(){ inti,j,k,count_cc=1;//當(dāng)count_cc=n時(shí)連通，否則不連通輸出nofound! intlength=0;//最小的公路總長度（即最小生成樹的代價(jià)） intlowcost[100],adjvex[100]; for(i=2;i<=n;i++)//初始化lowcost[]和adjvex[] { lowcost[i]=arc[1][i]; adjvex[i]=1; } lowcost[1]=0;//將頂點(diǎn)0加入集合U中 for(i=2;i<=n;i++) { intweight_min=10000;k=0; for(j=2;j<=n;j++) { if(lowcost[j]!=0&&lowcost[j]!=10000&&lowcost[j]<weight_min) {weight_min=lowcost[j];k=j;} } if(lowcost[k]==10000||k==0)break; count_cc++; length=length+lowcost[k]; lowcost[k]=0;//將頂點(diǎn)k加入集合U中 for(j=2;j<=n;j++)//調(diào)整lowcost和adjvex if(arc[k][j]<lowcost[j]) { lowcost[j]=arc[k][j];adjvex[j]=k; } } if(count_cc==n) cout<<length<<endl; elsecout<<"nofound!\n";}voidmain(){ intm,i,j,k,w;; while(cin>>n>>m) { if(n==0)return; for(i=1;i<=n;i++) {for(j=1;j<=n;j++){arc[i][j]=10000;}} for(i=1;i<=n;i++)arc[i][i]=0; for(k=0;k<m;k++)//依次輸入每一條邊，并修改鄰接矩陣的相應(yīng)元素 { cin>>i>>j>>w;//邊依附的兩個(gè)頂點(diǎn)的序號(hào) arc[i][j]=w;//置有邊標(biāo)志 arc[j][i]=w; } Prim(); } }第十二次作業(yè)：圖的最短路徑9092，9091，90859092:最短路

ProblemDescription“水上之都”威尼斯水城是個(gè)美麗的地方，ax幻想著某天能夠去那里旅游！

一天，ax想到一個(gè)問題：威尼斯由許多n個(gè)小島（由0到n-1編號(hào)）以及m座橋梁連成一體！假設(shè)ax在s號(hào)小島上，要去t號(hào)小島游玩！那么s到t的最短距離是多少！

Input本題目包含多組數(shù)據(jù)，每組數(shù)據(jù)第一行包含兩個(gè)正整數(shù)n和m(0<n<200,0<m<1000)，分別代表現(xiàn)有小島的數(shù)目和已修建橋梁的數(shù)目。接下來是m行橋梁的信息，每一行有三個(gè)整數(shù)A,B,X(0<=A,B<N,A!=B,0<X<10000),表示小島A和小島B之間有一條長度為X的橋梁：再接下一行有兩個(gè)整數(shù)s,t(0<=s,t<n)，分別代表起點(diǎn)和終點(diǎn)。

Output對(duì)于每組數(shù)據(jù)，請(qǐng)?jiān)谝恍欣镙敵鲎疃叹嚯x，如果不存在s到t的路徑則輸出"notfound!"。

SampleInput33011023121023101112

SampleOutput2notfound!//9092ANSWERCODE1#include<iostream>usingnamespacestd;intn,arc[200][200];voidDijk(intv,intv_end)//v源點(diǎn)，v_end終點(diǎn){ intdist[200],S[200],i,k,num,min; for(i=0;i<n;i++){dist[i]=arc[v][i];} S[0]=v;dist[v]=0;num=1; while(num<n)//當(dāng)S[]中的頂點(diǎn)數(shù)小于圖的頂點(diǎn)數(shù)時(shí)循環(huán) { min=10000;k=v;//min為dist[]最小值的下標(biāo)kfor(i=0;i<n;i++) { if(dist[i]!=0&&dist[i]<min) {min=dist[i];k=i;} } for(i=0;i<n;i++)//修改dist[] { if(dist[i]>dist[k]+arc[k][i]) { dist[i]=dist[k]+arc[k][i]; } } S[num++]=k;//將k加入集合S if(k==v_end&&dist[v_end]<10000) {cout<<dist[v_end]<<endl;return;} dist[k]=0;//置k為已生成終點(diǎn) } cout<<"notfound!\n";}voidmain(){ intm,s,t,i,j,k,w; while(cin>>n>>m) { for(i=0;i<n;i++){for(j=0;j<n;j++)arc[i][j]=10000;} for(i=0;i<n;i++)arc[i][i]=0; for(k=0;k<m;k++) {cin>>i>>j>>w;arc[i][j]=w;} cin>>s>>t; Dijk(s,t); } }9091:名次排序

ProblemDescription有N個(gè)比賽隊(duì)（1<=N<=500），編號(hào)依次為1，2，3，。。。。，N進(jìn)行比賽，比賽結(jié)束后，裁判委員會(huì)要將所有參賽隊(duì)伍從前往后依次排名，但現(xiàn)在裁判委員會(huì)不能直接獲得每個(gè)隊(duì)的比賽成績，只知道每場比賽的結(jié)果，即P1贏P2，用P1，P2表示，排名時(shí)P1在P2之前?，F(xiàn)在請(qǐng)你編程序確定排名。

Input輸入有若干組，每組中的第一行為二個(gè)數(shù)N（1<=N<=500）和M，其中N表示隊(duì)伍的個(gè)數(shù)，M表示接著有M行的輸入數(shù)據(jù)。接下來的M行數(shù)據(jù)中，每行也有兩個(gè)整數(shù)P1和P2，表示P1隊(duì)贏了P2隊(duì)。

Output給出一個(gè)符合要求的排名。輸出時(shí)隊(duì)伍號(hào)之間有空格，最后一名后面沒有空格。

其他說明：符合條件的排名可能不是唯一的，此時(shí)要求輸出時(shí)編號(hào)小的隊(duì)伍在前；輸入數(shù)據(jù)保證是正確的，即輸入數(shù)據(jù)確保一定能有一個(gè)符合要求的排名。

SampleInput43122343

SampleOutput1243//9091ANSWERCODE1#include<iostream>usingnamespacestd;intn,arc[500][500];voidmain(){ intm,i,j,k,f,num,indg[500],visit[500]; while(cin>>n>>m) { for(i=1;i<=n;i++){for(j=1;j<=n;j++)arc[i][j]=0;} for(k=0;k<m;k++){cin>>i>>j;arc[i][j]=1;} for(i=1;i<=n;i++){indg[i]=0;visit[i]=0;} for(j=1;j<=n;j++) {for(i=1;i<=n;i++){indg[j]+=arc[i][j];}} f=0;num=0; while(num<n) { for(i=1;i<=n;i++) { if(indg[i]==0&&visit[i