並查集

2/10ページ

【bzoj1370】[Baltic2003]Gang團伙

Description 在某城市裡住著n個人,任何兩個認識的人不是朋友就是敵人,而且滿足: 1、 我朋友的朋友是我的朋友; 2、 我敵人的敵人是我的朋友; 所有是朋友的人組成一個團伙。告訴你關於這n個人的m條資訊,即某兩個人是朋友,或者某兩個人是敵人,請你編寫一個程式,計算出這個城市最多可能有多少個 […]

bzoj 3319: 黑白樹 (並查集)

題目描述 傳送門 題目大意:給定一棵樹,邊的顏色為黑或白,初始時全部為白色。維護兩個操作: 1.查詢u到根路徑上的第一條黑色邊的標號。 2.將u到v 路徑上的所有邊的顏色設為黑色。 Notice:這棵樹的根節點為1 題解 先將所有操作正著進行一遍,將所有的黑邊相鄰的點按照關係合併,就是一個集合中的代 […]

最近公共祖先(LCA)及其倍增演算法實現

最近公共祖先(LCA) 今天看看最近公共祖先(LCA),也就是所謂的最小公共祖先。 我們首先了解一下什麼是LCA,我們通過幾棵樹來理解一下吧。 如圖所示,這棵樹是以1為根節點的一棵樹,我們舉一個例子,3和5的LCA就是2,4和5的LCA就是1,3和2的LCA就是2本身。是不是有點明白? 接下來,我們 […]

並查集與十度好友

一、問題簡介     首先說下問題吧,這裡就不做廣告了,在社交網路中,假設A和B是好友,B和C是好友,如果A和C不是好友,那麼就說C是A的二度好友,在一個有10萬人人際網路中,如何在時間O(n)時間裡,找到某個人的十度好友。     查了下網上人們對這個問題解法的思路,大致有兩種觀點:(1)BFS; […]

演算法基礎 – 並查集

並查集 在一些有N個元素的集合應用問題中,我們通常是在開始時讓每個元素構成一個單元素的集合,然後按一定順序將屬於同一組的元素所在的集合合併,其間要反覆查詢一個元素在哪個集合中。這一類問題近幾年來反覆出現在資訊學的國際國內賽題中,其特點是看似並不複雜,但資料量極大,若用正常的資料結構來描述的話,往往在 […]

並查集詳解 ——圖文解說,簡單易懂(轉)

並查集是我暑假從高手那裡學到的一招,覺得真是太精妙的設計了。以前我無法解決的一類問題竟然可以用如此簡單高效的方法搞定。不分享出來真是對不起party了。(party:我靠,關我嘛事啊?我跟你很熟麼?) 來看一個例項,HDU1232暢通工程 首先在地圖上給你若干個城鎮,這些城鎮都可以看作點,然後告訴你 […]