| ||||||||||
| 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