1699 問題 K: 數(shù)據(jù)結(jié)構(gòu)-用樹表示的等價問題
時間限制: 1s
內(nèi)存限制: 32MB 提交: 98 解決: 55
題目描述
在離散數(shù)學中，對等價關(guān)系和等價類的定義是：
如果集合S中的關(guān)系R是自反的、對稱的和傳遞的，則稱它為一個等價關(guān)系。
等價關(guān)系是現(xiàn)實世界中廣泛存在的一種關(guān)系，許多應用問題可以歸結(jié)至等價類問題，這類問題通常被稱為等價問題。
通過使用集合，能夠解決等價問題。而集合可以通過雙親表示法的樹結(jié)構(gòu)進行保存。通過對樹結(jié)構(gòu)的操作，可以實現(xiàn)查找、歸并等操作。查找操作和歸并操作的算法如下：
在以上的歸并操作中，由于表示集合的樹的深度與樹形成的過程有關(guā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
提示
比賽公告
話不多說，我就是湊字數(shù)。卡卡卡卡卡卡卡卡卡卡卡哈哈哈哈哈哈哈啊嗝