、劃分江湖上大俠門派問題----等價類劃分問題
-----（并查集的應用）
1. 問題描述
如果某種關系具有自反性，對稱性和傳遞性，那么就稱這種關系為等價關系。自反性就是任何一個事物總可以和自己有這樣的關系；比如：血型相同的關系，自己和自己總是血型相同的關系；對稱性是如果A事物和B事物有這樣的關系，則B事物也和A事物有這種關系；比如：血型相同的關系，顯然是滿足這個條件的；傳遞性則是說如果A事物和B事物有此關系，B事物和C事物也有這種關系，那么A和C有此關系。又比如：血型相同關系，A與B血型相同，B與C血型相同，則A與C血型相同，所以血型相同關系是等價關系。若將同一種血型看成是一個等價類，劃分出不同血型的群體就變成了等價類劃分問題。
傳說江湖散落著各種大俠，整天沒事兒干，背個劍走來走去，碰到和自己不是同一門派的人，就打一架。但是他們很講義氣，絕對不打自己的朋友。而且他們信奉“朋友的朋友就是我的朋友”。只要是能通過朋友關系串聯起來的，不管拐了多少個彎，都認為是自己人，江湖上就形成了一個一個的門派，通過兩兩之間的朋友關系串聯起來。于是在同一個門派的人就可以放心往死了打。我們可以在每個門派內推舉出一個比較有名望的人，作為該門派的掌門人，這個人就是他們的老大。
例如：有10個大俠，編號分別是1-10，有11條朋友關系：（6,1），（5,4），（4,9），（7,6），（10,5），(3,2)，(9,10)，（8,3），（7,2），（2,1），（7,8），其中（6,1）表示編號6的人與編號1的人是，其余類似。可以得出（1,2,3,6,7,8）這六個人屬于同一個門派，（4,5,9,10）這4個人屬于同一個門派，整個江湖共有2個門派。
我們的任務是找出江湖上大俠的門派劃分。顯然一門派可以看成是一個等價類，因而劃分門派問題就變成了等價類劃分問題。
2. 設計要求
輸入設計：輸入等價關系對（即朋友關系對）。
輸出設計：找出江湖上共有多少個門派，并按門派輸出所有大俠。
3. 設計思想
本問題可以利用并查集實作。并查集是一種抽象資料型別，它是若干個不相交的動態集合的集合S={A，B，…}，支持以下的運算：
?MakeSet(x): 構造一個集合，它只包含一個元素x;
?Union(x,y): 將x所在集合和y所在的集合合并成一個集合;
?Find (x): 找出元素x所在集合。
（1）資料結構設計
在本問題中，可以將每個門派（等價類）描述為一個樹，樹中每個非根結點都指向其雙親結點（直接上司），用根元素（掌門人）作為門派（等價類）的標識，整個江湖可看成是一個森林。例如現在江湖有兩個門派，分成如圖1所示的層次關系。該森林可用雙親表示法存盤表示。
圖1 江湖門派層次示意圖
為了最后能按幫派輸出大俠, 可為每個幫派設一條鏈，每條鏈都設首尾指標，從而使得合并兩個鏈表時效率較高。
（2）演算法設計
假設江湖上共有n個大俠，初始時，每個人都是一個獨立的門派（等價類），可用MakeSet(x)實作。
有一天，藍炳走在路上，碰到了楊再寧，兩人一言不合就想開打，但在開打之前他們需要先逐級查詢自己的老大。發現老大不是一個人，于是今日注定不太平。打完以后決定認個朋友。每加入一個朋友關系（x，y），先查看x和y都屬于哪個門派（等價類），可用Find (x)和Find(y)實作，即分別找出x與y所在樹的根結點（門派老大）。
若每次查詢都做優化處理，使整個門派樹的層數都會維持在比較低的水平上，則檢索效率會更高。比如，藍丙和馮旭都直接做掌門人的直接下屬，如圖2所示。
如果x和y屬于同一個門派（等價類），即他們的老大（所在的樹根）是同一個，則關系（x，y）不用處理；否則，將x所在的門派（等價類）和y所在的門派（等價類）合并成一個門派（等價類），可用Union(x,y)實作，即將x所在的樹與x所在的樹合并為一棵樹。
圖2 查詢時進行處理的示意圖
有一天，藍炳走在路上，碰到了楊再寧，兩人一言不合就想開打，但在開打之前他們需要先逐級查詢自己的老大。發現老大不是一個人，于是今日注定不太平。打完以后決定認個朋友，從而導致兩個門派合并，那么誰當老大呢？一種方案是原來的兩個老大中誰當合并后門派的老大都可以。還有一種方案是按江湖規矩，大幫派的老大成為合并后新幫派的老大，如圖3和圖4所示。第二種方案有利于提高檢索速度。
圖3 未壓縮路徑時小門派合并到大門派示意圖
圖4 壓縮路徑時小門派合并到大門派示意圖
合并兩個幫派時，可將兩個幫派對應的鏈表首尾相連。
uj5u.com熱心網友回復：
矩陣運算。。。。。。。。轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/97384.html
標籤：C語言
上一篇：switch問題
下一篇：為什么測驗平臺不認同我的啊