题解 P1394 【山上的国度】

皮卡丘最萌 · 2019-07-31 19:24:11 · 题解

蒟蒻来水一发PASCAL题解。

I)题目的意思非常明确：水往低处流。所以当最高点有2个及以上时，直接输出Non。

例如有5个数：1 2 3 4 3，这是就直接输出Non。

II)题目输入连接的边后，仍然无法连通，直接输出Non。（这个可以用并查集来判定）

例如有6个村庄，5条边：1-2 1-3 5-6 2-3 6-4

这时就会有2个集合(1,2,3),(4,5,6),直接输出Non。

III)排除这2种情况，就直接输出最高村庄的编号。

具体看程序：

var n,m,i,x,max,max1,max2,y,x1,y1:longint;
f:array[0..100001] of longint;
function find(x:longint):longint;          //寻找根节点
begin
if f[x]=x then exit(x);
f[x]:=find(f[x]);
exit(f[x]);
end;

begin
readln(n,m);
for i:=1 to n do
  begin
  read(x);
  if x>max then                                 //求最大
    begin max:=x; max1:=1; max2:=i; end;   //保存最大的值，个数，位置
  if (x=max)and(i<>max2) then inc(max1);      //把相同的最大值个数+1
  end;
if max1<>1 then writeln('Non')             //最高节点有多个，直接输出
  else
    begin
    for i:=1 to n do f[i]:=i;                //默认根节点为自己
    for i:=1 to m do
      begin
      readln(x,y);
      x1:=find(x); y1:=find(y);              //找祖先
      if x1<>y1 then f[x1]:=y1;               //连边
      end;
    for i:=1 to n do
      if find(i)<>find(1) then
        begin writeln('Non'); halt; end;     
                         //没有同一祖先，即没有联通，直接输出
    writeln('Oui, j',chr(ord('''')),'ai trouve la solution.');
                   //按格式输出，由于PASCAL不能直接输出'，所以比较奇怪
    writeln(max2); //输出位置
    end;
end.