破碎的路径

2024-01-29 20:38

文章标签 路径破碎

本文主要是介绍破碎的路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

比尔去很多地方旅游过。他在旅游的同时留下了很多简短的旅行笔记。笔记的形式是这样的：
出发地目的地
如下面就是三条合法的note:
SwimmingPool OldTree
BirdsNest Garage
Garage SwimmingPool
在某一次搬家的时候，比尔的笔记本不小心散架了。于是他的笔记的顺序被完全打乱了。他想请你帮个忙，帮他把这些笔记的顺序整理好，先写的笔记在前面。幸运的是，同一个地方比尔至多只去过一次。也就是说，在这些笔记当中，一个地方至多出现两次，一次作为目的地，一次作为出发地。

Input

第一行是一个整数ｎ，表示笔记的条数。N <= 12000。接下来有ｎ行，每行一条笔记。笔记的两个单词的长度都不会超过15，两个单词之间以一个空格分隔。

Output

输出整理好顺序的笔记.

Sample Input

3
SwimmingPool OldTree
BirdsNest Garage
Garage SwimmingPool

Sample Output

BirdsNest Garage
Garage SwimmingPool
SwimmingPool OldTree

Data Constraint

Hint

【限制】
对于50%的数据，n <= 1000。
对于100%的数据，n <= 12000。

分析
看题我们知道——这是一条链
我用了哈希，确定字符串的编号
如果在读入中哈希表判断已出现的，那么肯定同时作为出发地和目的地出现过，那么这个点很明显就是中间的点
然后一遍遍历一边输出即可

程序：

var
u,v:array[0..12000]of longint;
s1,s2:array[0..12000]of string;
son:array[0..60000]of longint;
hash:array[0..60000]of string;
n,s:longint;
b,p:array[0..60000]of boolean;
zfc:string;
function locate(s:string):longint;
var
l,h,k,i:longint;
beginl:=length(s);h:=0;k:=1;for i:=0 to l-1 dobeginh:=h+(ord(s[i])*k) mod 56399;k:=k*10 mod 56399;end;while (hash[(h+i) mod 56399]<>'')and(hash[(h+i) mod 56399]<>s) do inc(i);exit((h+i) mod 56399);
end;procedure insert(s:string);
var
i:longint;
begini:=locate(s);hash[i]:=s;
end;function member(s:string):boolean;
var
i:longint;
begini:=locate(s);if hash[i]=s then exit(true) else exit(false);
end;procedure init;
var
count,i:longint;
beginreadln(n);count:=0;while (count<n) dobeginreadln(zfc);s1[count]:=copy(zfc,1,pos(' ',zfc)-1);s2[count]:=copy(zfc,pos(' ',zfc)+1,length(zfc)-pos(' ',zfc));if (member(s1[count])=true) then p[locate(s1[count])]:=true else insert(s1[count]);if (member(s2[count])=true) then p[locate(s2[count])]:=true else insert(s2[count]);inc(count);u[count]:=locate(s1[count-1]);v[count]:=locate(s2[count-1]);son[u[count]]:=count;end;for count:=0 to n-1 doif (p[locate(s1[count])]=false) then s:=locate(s1[count]);
end;procedure print;
var
i:longint;
begini:=son[s];while (i>0) dobeginwriteln(hash[u[i]],' ',hash[v[i]]);i:=son[v[i]];end;
end;begininit;print;
end.