Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我快WA疯了,求好心的大神和我看看怎么错了,感激不尽(有注释)var t,n,i,x,y,tot,tt,tat,s,cnt:longint; head,mark1,mark2:array[-1..30] of longint; next,l,num,sta:array[0..5000] of longint; v,find:array[0..30] of boolean; flag:array[0..5000] of boolean; word:array[0..2000] of string; procedure get(x,y,i:longint);//用一个链表存边,同时排序 var tmp:longint; begin inc(tot); next[tot]:=head[x]; head[x]:=tot; l[tot]:=y; num[tot]:=i; tmp:=tot; while next[tmp]<>0 do begin if word[num[tmp]]>word[num[next[tmp]]] then begin y:=l[tmp];l[tmp]:=l[next[tmp]];l[next[tmp]]:=y; y:=num[tmp];num[tmp]:=num[next[tmp]];num[next[tmp]]:=y; tmp:=next[tmp]; end else break; end; end; procedure dfsc(x:longint);//用来判断一个图是否连通的 var now:longint; begin find[x]:=true; inc(tt); now:=head[x]; while now<>0 do begin if not find[l[now]] then dfsc(l[now]); now:=next[now]; end; end; function check:boolean;//用来判断是否可行 var i,cnt1,cnt2:longint; begin cnt1:=0;cnt2:=0; for i:=1 to 26 do if mark1[i]>0 then begin tt:=0;dfsc(i);s:=i;break;end; if tt<>cnt then exit(false); //这一部分判断是否连通,同时找到到时DFS的第一个点。cnt是总点数,tt是一次DFS找到的总点数 for i:=1 to 26 do begin if abs(mark1[i]-mark2[i])>1 then exit(false); if mark1[i]-mark2[i]=1 then begin inc(cnt1);s:=i;end; if mark2[i]-mark1[i]=1 then inc(cnt2); end; //cnt1是出度-入度大于1的点数,cnt2是入度-出度大于1的点数,同时找到如果是欧拉路径的话搜索的第一个点,mark1是一点的出度,mark2是出度 if (cnt1>1) or (cnt2>1) then exit(false); if cnt1+cnt2=1 then exit(false); exit(true); end; procedure dfs(x,e:longint);//用来找路径 var now:longint; begin flag[e]:=true;//flag记录每个点是否被访问。 now:=head[x]; while now<>0 do begin if not flag[now] then dfs(l[now],now); now:=next[now]; end; inc(tat);sta[tat]:=e;//sta是一个栈,用来存边 end; procedure main;// 主过程 begin fillchar(head,sizeof(head),0); fillchar(v,sizeof(v),0); fillchar(find,sizeof(find),0); fillchar(mark1,sizeof(mark1),0); fillchar(mark2,sizeof(mark2),0); fillchar(flag,sizeof(flag),0); cnt:=0;tot:=0;//各种初始化 readln(n); for i:=1 to n do begin readln(word[i]); x:=ord(word[i][1])-96; y:=ord(word[i][length(word[i])])-96; get(x,y,i); inc(mark1[x]);inc(mark2[y]); if not v[x] then begin v[x]:=true;inc(cnt);end; if not v[y] then begin v[y]:=true;inc(cnt);end; end; if not check then begin writeln('***');exit;end; tat:=0; dfs(s,0); for i:=tat-1 downto 2 do write(word[num[sta[i]]],'.');writeln(word[num[sta[1]]]); end; begin readln(t); while t>0 do begin dec(t);main;end; end. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator