並查集

1/10ページ

星球聯盟

題目描述 在遙遠的S星系中一共有N個星球,編號為1…N。其中的一些星球決定組成聯盟,以方便相互間的交流。 但是,組成聯盟的首要條件就是交通條件。初始時,在這N個星球間有M條太空隧道。每條太空隧道連線兩個星球,使得它們能夠相互到達。若兩個星球屬於同一個聯盟,則必須存在一條環形線路經過這兩個星球,即兩個 […]

[Baltic2003]gang團伙

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

bzoj1370 團伙 【並查集】

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

bzoj1370 團伙

團伙 題目背景: bzoj1370 分析:並查集,對於兩個敵人,將x與y n,y與x n,合併,然後對於朋友,將x與y合併,然後就可以符合題目要求了,敵人的敵人是朋友,朋友的朋友是朋友,注意對於朋友,x n與y n不能合併,因為沒有說朋友的敵人一定是敵人。最後統計1 ~ n中有多少集合就可以了 So […]