我都对了数据 就是有几个safe 我输出的cc cry 这是为什么
请牛来看下。。。10分悬的。
状态: Unaccepted
测评机： Xeost[5]
得分： 20分
提交日期： 2010-10-3 22:59:00
有效耗时： 344毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 通过本测试点|有效耗时172ms
测试结果3: 测试结果错误
。错误
。错误
。错误
。错误
。错误
。错误
。错误
program v379;
type treenode=record
name:string; /这个是数组类型/
father:longint;
end;
var a:array[1..2008]of treenode;
i,j,k,n,m,h1,h2,p,q,len:longint;
x,y,z:string;
function getfather(x:longint):longint;
begin
if a[x].father=x
then getfather:=x
else /找最远祖先+压缩/
begin
a[x].father:=getfather(a[x].father);
getfather:=a[x].father;
end;
end;
procedure union(x,y:longint);
begin
p:=getfather(x);
q:=getfather(y);
if p<>q /合并/
then a[p].father:=q;
end;
function judge(x,y:longint):boolean;
begin
if getfather(x)=getfather(y)
then judge:=true
else judge:=false; /判断是不是朋友/
end;
begin
assign(input,'v379.in');
assign(output,'v379.out');
reset(input);
rewrite(output);
readln(n,m,k);
for i:=1 to n do
begin
readln(a[i].name); /读入名字/
a[i].father:=i;
end;
for i:=1 to m do
begin
readln(z);
j:=pos(' ',z);
len:=length(z);
x:=copy(z,1,j-1);
y:=copy(z,j+1,len-j);
h1:=0;
h2:=0;
for j:=1 to n do /读入2到n+1行的数据x y是分解出的名称/
begin /h1 h2用来找名称所在的点编号，找到后合并/
if a[j].name=x then h1:=j;
if a[j].name=y then h2:=j;
if h1*h2<>0 then break;
end;
union(h1,h2);
end;
for i:=1 to k do
begin
readln(z);
j:=pos(' ',z);
len:=length(z);
x:=copy(z,1,j-1);
y:=copy(z,j+1,len-j);
h1:=0; /读入带两个mm的名字x y h1 h2和上面循环一样/
h2:=0;
for j:=1 to n do /然后判断h1 h2两个点有没有共同的最远祖先/
begin
if a[j].name=x then h1:=j;
if a[j].name=y then h2:=j;
if h1*h2<>0 then break;
end;
if judge(h1,h2)
then writeln('safe')
else writeln('cc cry');
end;
close(input);
close(output);
end.
大牛来帮我看下吧 我都郁闷死了这题
丑陋的代码:
var
mm:array[1..2008] of string;
father:array[1..2008] of longint;
st,st1,st2:string;
n,m,p,i,t1,t2,f1,f2:longint;
function search(s:string):longint;
var
i:longint;
begin
for i:=1 to n do
if mm[i]=s then exit(i);
end;
function getfather(v:longint):Longint;
begin
if father[v]=0 then
getfather:=v
else
begin
father[v]:=getfather(father[v]);
getfather:=father[v];
end;
end;
begin
readln(n,m,p);
for i:=1 to n do readln(mm[i]);
fillchar(father,sizeof(father),0);
for i:=1 to m do
begin
readln(st);
st1:=copy(st,1,pos(' ',st)-1);
st2:=copy(st,pos(' ',st)+1,length(st)-pos(' ',st));
t1:=search(st1);
t2:=search(st2);
f1:=getfather(t1);
f2:=getfather(t2);
if f1<>f2 then father[f2]:=f1;
end;
for i:=1 to p do
begin
readln(st);
st1:=copy(st,1,pos(' ',st)-1);
st2:=copy(st,pos(' ',st)+1,length(st)-pos(' ',st));
t1:=search(st1);
t2:=search(st2);
f1:=getfather(t1);
f2:=getfather(t2);
if f1=f2 then writeln('safe') else writeln('cc cry');
end;
end.
每个元素所在集合的代表最好单独用个数组来记录,可能是这里有问题
var
n,m,p:longint;
s:array[1..2008] of string;
father:array[1..2008] of longint;
q,p1,p2:string;
k,g1,g2,i:longint;
f1,f2:boolean;
function find(i:longint):longint;
begin
if (father[i]=i) then exit(i);
father[i]:=find(father[i]);
exit(father[i]);
end;
begin
readln(n,m,p);
for i:=1 to n do
begin readln(s[i]); father[i]:=i; end;
for i:=1 to m do
begin
readln(q);
k:=pos(' ',q);
p1:=copy(q,1,k-1);
p2:=copy(q,k+1,length(q)-k);
g1:=1;g2:=1;
f1:=true; f2:=true;
k:=1;
while (f1 or f2) do
begin
if s[k]=p1 then begin g1:=k; f1:=false; end;
if s[k]=p2 then begin g2:=k; f2:=false; end;
inc(k);
end;
g1:=find(g1);
g2:=find(g2);
if g1<>g2 then father[g1]:=g2;
end;
for i:=1 to n do father[i]:=find(i);
for i:=1 to p do
begin
readln(q);
k:=pos(' ',q);
p1:=copy(q,1,k-1);
p2:=copy(q,k+1,length(q)-k);
g1:=1;g2:=1;
f1:=true; f2:=true;
k:=1;
while (f1 or f2) do
begin
if s[i]=p1 then begin g1:=i; f1:=false; end;
if s[i]=p2 then begin g2:=i; f2:=false; end;
end;
g1:=find(g1);
g2:=find(g2);
if g1=g2 then writeln('safe') else writeln('cc cry');
end;
end.