題目 1699:
數(shù)據(jù)結構-用樹表示的等價問題
時間限制: 2s
內存限制: 96MB 提交: 83 解決: 50
題目描述
在離散數(shù)學中，對等價關系和等價類的定義是：
如果集合S中的關系R是自反的、對稱的和傳遞的，則稱它為一個等價關系。
等價關系是現(xiàn)實世界中廣泛存在的一種關系，許多應用問題可以歸結至等價類問題，這類問題通常被稱為等價問題。
通過使用集合，能夠解決等價問題。而集合可以通過雙親表示法的樹結構進行保存。通過對樹結構的操作，可以實現(xiàn)查找、歸并等操作。查找操作和歸并操作的算法如下：
在以上的歸并操作中，由于表示集合的樹的深度與樹形成的過程有關，因此在最壞情況下全部歸并操作將會有O(n2)的復雜度。而通過在歸并時比較子集所含成員的數(shù)目，令成員少的歸并至成員多的集合，將能夠提高算法的效率。下面給出優(yōu)化的歸并操作算法：
另外，通過增加“壓縮路徑”的功能，即將所有從根到相應元素路徑上的元素都變成樹根的孩子。算法如下所示：
本題中，將會給出n個原本互不相交的集合及k次集合合并的操作。通過這k次合并，判斷最終的某兩個原始的集合是否被合并成了同一個集合。
輸入格式
輸入的第一行包含兩個用空格隔開的正整數(shù)n和k，其中n不超過100，k不超過n-1。
之后的k行中，每行包含兩個用空格隔開的正整數(shù)x和y，表示將x元素所在的集合和y元素所在的集合合并至同一個集合。保證x和y均在1至n之間。
最后一行中，包含兩個正整數(shù)，表示需要判斷是否在同一個集合的元素編號。
輸出格式
共一行，包含字符串“YES”或“NO”，“YES”表示需判斷的元素在同一個集合中，“NO”表示不在同一個集合中。請注意不需要輸出引號，且行尾輸出換行。
樣例輸入
5 2 1 3 2 3 1 2
樣例輸出
YES