給定一個(gè)沒有重復(fù)值的整形數(shù)組arr，初始時(shí)認(rèn)為arr中每一個(gè)數(shù)各自都是一個(gè)單獨(dú)的集合。請(qǐng)?jiān)O(shè)計(jì)一種叫UnionFind的結(jié)構(gòu)，并提供以下兩個(gè)操作。 boolean isSameSet(int a, int b): 查詢a和b這兩個(gè)數(shù)是否屬于一個(gè)集合 void union(int a, int b): 把a(bǔ)所在的集合與b所在的集合合并在一起，原本兩個(gè)集合各自的元素以后都算作同一個(gè)集合 [要求] 如果調(diào)用isSameSet和union的總次數(shù)逼近或超過O(N)，請(qǐng)做到單次調(diào)用isSameSet或union方法的平均時(shí)間復(fù)雜度為O(1)
輸入描述:
第一行兩個(gè)整數(shù)N, M。分別表示數(shù)組大小、操作次數(shù)接下來M行，每行有一個(gè)整數(shù)opt若opt = 1，后面有兩個(gè)數(shù)x, y，表示查詢(x, y)這兩個(gè)數(shù)是否屬于同一個(gè)集合若opt = 2，后面有兩個(gè)數(shù)x, y，表示把x, y所在的集合合并在一起
輸出描述:
對(duì)于每個(gè)opt = 1的操作，若為真則輸出"Yes"，否則輸出"No"
示例1
輸入
4 5
1 1 2
2 2 3
2 1 3
1 1 1
1 2 3
說明
每次2操作后的集合為
({1}, {2}, {3}, {4})
({1}, {2, 3}, {4})
({1, 2, 3}, {4})
加載中...