think: 1并查集開始時(shí)候感覺有點(diǎn)像初級的桶排序，先將一個(gè)個(gè)元素作為一個(gè)個(gè)小的區(qū)間，然后在不斷地查詢過程中進(jìn)行區(qū)間的合并，通過建立一種樹結(jié)構(gòu)進(jìn)而加快了查詢速度，感覺這種樹結(jié)構(gòu)和之前練習(xí)的二叉樹題目不是很像，更像是一種集合的映射，或者因?yàn)樽约褐暗亩鏄洳糠挚赡苓^多的注意模板，少了很多思考，感覺其實(shí)樹結(jié)構(gòu)像是借助基本數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)一種解決問題的思想
sdut原題鏈接
小雷的冰茶幾 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 小雷有個(gè)特殊的癖好，平時(shí)喜歡收藏各種稀奇古怪的東西，譬如。。。。,還有。。。。，也包括。。。。。小雷是一個(gè)喜歡分享的童鞋，這次小雷又給大家?guī)硪惶咨衿娴臇|西，那就是舉世無雙的冰茶幾！ 顧名思義，這些茶幾被冰凍住了，最主要的是他們是易碎品，畢竟被凍住了。因此小雷要很小心翼翼的移動他們。一些茶幾是凍在一起的，因此一套冰茶幾分為好幾部分，并且如果茶幾A與B凍在一起，B與C凍在一起，那么A與C也就凍在了，即冰凍狀態(tài)有傳遞性，ABC此時(shí)會看作一個(gè)整體。 為了保證冰茶幾的完整性，小雷每次只能移動一整塊冰茶幾，也就是冰凍在一起的一部分。小雷想知道他需要搬幾次才能全部搬到實(shí)驗(yàn)室，你能幫小雷快速計(jì)算出答案么？
Input 多組輸入，先輸入組數(shù)T（1 < = T < = 200）。 對于每組輸入，先輸入一個(gè)整數(shù)n（1 < = n < = 100000），k（0 < = k < = 100000），茶幾編號1~n。 之后k行，每行兩數(shù)x，y（1 < = x，y < = n），表示第x個(gè)茶幾和第y個(gè)茶幾冰凍在一起。
Output 對于每組輸入，先輸出”Case z: ”（不帶引號）表示組數(shù)，再輸出一個(gè)整數(shù)，表示小雷需要搬動的次數(shù)。
Example Input 3 3 1 1 2 5 2 1 2 3 4 5 2 1 2 2 3
Example Output Case 1: 2 Case 2: 3 Case 3: 3
Hint
Author 2015年第五屆ACM趣味編程循環(huán)賽(第一場) by LeiQ
以下為accepted代碼——非遞歸
#include <stdio.h>#include <string.h>int f[100004];void init(int n){ for(int i = 1; i <= n; i++) f[i] = i;}int getf(int v){ while(v != f[v]) { v = f[v]; } return v;}void merge(int u, int v){ int t1 = getf(u); int t2 = getf(v); if(t1 != t2) f[t1] = t2;}int main(){ int n, m, T, k, i, sum, u, v; scanf("%d", &T); for(k = 1; k <= T; k++) { sum = 0; scanf("%d %d", &n, &m); init(n); for(i = 0; i < m; i++) { scanf("%d %d", &u, &v); merge(u, v); } for(i = 1; i <= n; i++) { if(f[i] == i) sum += 1; } printf("Case %d: %d/n", k, sum); } return 0;}/***************************************************User name: Result: AcceptedTake time: 104msTake Memory: 500KBSubmit time: 2017-02-20 20:07:00****************************************************/以下為accepted代碼——遞歸
#include <stdio.h>#include <string.h>int f[100004];void init(int n){ for(int i = 1; i <= n; i++) f[i] = i;}int getf(int v){ if(f[v] == v) return v; else { f[v] = getf(f[v]); return f[v]; }}void merge(int u, int v){ int t1 = getf(u); int t2 = getf(v); if(t1 != t2) f[t1] = t2;}int main(){ int T, n, m, k, i, sum, u, v; scanf("%d", &T); for(k = 1; k <= T; k++) { sum = 0; scanf("%d %d", &n, &m); init(n); for(i = 0; i < m; i++) { scanf("%d %d", &u, &v); merge(u, v); } for(i = 1; i <= n; i++) { if(f[i] == i) sum += 1; } printf("Case %d: %d/n", k, sum); } return 0;}/***************************************************User name: Result: AcceptedTake time: 104msTake Memory: 2056KBSubmit time: 2017-02-20 19:59:40****************************************************/新聞熱點(diǎn)
疑難解答
