二叉樹的建樹

建議使用結(jié)構(gòu)體建立二叉樹，優(yōu)點是內(nèi)存占用低:

使用遞歸建樹:

L2-3 二叉搜索樹的2層結(jié)點統(tǒng)計

二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點的值均小于或等于它的根結(jié)點的值；若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；它的左、右子樹也分別為二叉搜索樹。

將一系列數(shù)字按給定順序插入一棵初始為空的二叉搜索樹，你的任務是統(tǒng)計結(jié)果樹中最下面 2 層的結(jié)點數(shù)。

輸入格式：輸入在第一行給出一個正整數(shù)?N?(≤1000)，為插入數(shù)字的個數(shù)。第二行給出?N?個?[?1000,1000]?區(qū)間內(nèi)的整數(shù)。數(shù)字間以空格分隔。

輸出格式：在一行中輸出最下面 2 層的結(jié)點總數(shù)。

輸入樣例：9
25 30 42 16 20 20 35 -5 28
輸出樣例：6

可以用dfs解決:

當然bfs也行， 也稱為層序遍歷:

L2-1 分而治之(鏈式前向星 + 模擬)

分而治之，各個擊破是兵家常用的策略之一。在戰(zhàn)爭中，我們希望首先攻下敵方的部分城市，使其剩余的城市變成孤立無援，然后再分頭各個擊破。為此參謀部提供了若干打擊方案。本題就請你編寫程序，判斷每個方案的可行性。

輸入格式：

輸入在第一行給出兩個正整數(shù) N 和 M（均不超過10 000），分別為敵方城市個數(shù)（于是默認城市從 1 到 N 編號）和連接兩城市的通路條數(shù)。隨后 M 行，每行給出一條通路所連接的兩個城市的編號，其間以一個空格分隔。在城市信息之后給出參謀部的系列方案，即一個正整數(shù) K （≤?100）和隨后的 K 行方案，每行按以下格式給出：

Np v[1] v[2] ... v[Np]

其中?Np?是該方案中計劃攻下的城市數(shù)量，后面的系列?v[i]?是計劃攻下的城市編號。

輸出格式：

對每一套方案，如果可行就輸出YES，否則輸出NO。

輸入樣例：

10 11 8 7 6 8 4 5 8 4 8 1 1 2 1 4 9 8 9 1 1 10 2 4 5 4 10 3 8 4 6 6 1 7 5 4 9 3 1 8 4 2 2 8 7 9 8 7 6 5 4 2

輸出樣例：

NO YES YES NO NO

分析: 為了節(jié)省內(nèi)存運用鏈式前向星建圖。。。

鏈式前向星建圖模板:

遍歷, i 代表某一個節(jié)點:

完整代碼:

L1-1 天梯賽座位分配 (二維數(shù)組模擬)

天梯賽每年有大量參賽隊員，要保證同一所學校的所有隊員都不能相鄰，分配座位就成為一件比較麻煩的事情。為此我們制定如下策略：假設某賽場有 N 所學校參賽，第 i 所學校有 M[i] 支隊伍，每隊 10 位參賽選手。令每校選手排成一列縱隊，第 i+1 隊的選手排在第 i 隊選手之后。從第 1 所學校開始，各校的第 1 位隊員順次入座，然后是各校的第 2 位隊員…… 以此類推。如果最后只剩下 1 所學校的隊伍還沒有分配座位，則需要安排他們的隊員隔位就坐。本題就要求你編寫程序，自動為各校生成隊員的座位號，從 1 開始編號。

輸入格式：

輸入在一行中給出參賽的高校數(shù) N （不超過100的正整數(shù)）；第二行給出 N 個不超過10的正整數(shù)，其中第 i 個數(shù)對應第 i 所高校的參賽隊伍數(shù)，數(shù)字間以空格分隔。

輸出格式：

從第 1 所高校的第 1 支隊伍開始，順次輸出隊員的座位號。每隊占一行，座位號間以 1 個空格分隔，行首尾不得有多余空格。另外，每所高校的第一行按“#X”輸出該校的編號X，從 1 開始。

輸入樣例：

3 3 4 2

輸出樣例：

#1 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 63 65 67 69 71 73 75 77 79 #2 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 #3 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60

分析: 我們利用一個二維數(shù)組來存儲每個學校選手的位置:

school[i][j]: 代表第 i 個學校的第 J 個學生的座位。然后根據(jù)題目模擬更新 school 數(shù)組:

注意當只剩下 1 所學校的隊伍還沒有分配座位，需要安排他們的隊員隔位就坐, 也就是我們遍歷的時候當 school[i][j-1]+1=school[i][j] 并且 i != 1的時候, 這時候我們要再讓 school[i][j] 自增一次:

L3-1 社交集群(并查集)

當你在社交網(wǎng)絡平臺注冊時，一般總是被要求填寫你的個人興趣愛好，以便找到具有相同興趣愛好的潛在的朋友。一個“社交集群”是指部分興趣愛好相同的人的集合。你需要找出所有的社交集群。

輸入格式：

輸入在第一行給出一個正整數(shù) N（≤1000），為社交網(wǎng)絡平臺注冊的所有用戶的人數(shù)。于是這些人從 1 到 N 編號。隨后 N 行，每行按以下格式給出一個人的興趣愛好列表：

Ki:?hi[1]?hi[2]?...?hi[Ki]

其中Ki(>0)是興趣愛好的個數(shù)，hi[j]是第j個興趣愛好的編號，為區(qū)間 [1, 1000] 內(nèi)的整數(shù)。

輸出格式：

首先在一行中輸出不同的社交集群的個數(shù)。隨后第二行按非增序輸出每個集群中的人數(shù)。數(shù)字間以一個空格分隔，行末不得有多余空格。

輸入樣例：

8 3: 2 7 10 1: 4 2: 5 3 1: 4 1: 3 1: 4 4: 6 8 1 5 1: 4

輸出樣例：

3 4 3 1

這是一個經(jīng)典的并查集思想, 我們可以按興趣來將人分堆, 然后運用并查集這種數(shù)據(jù)結(jié)果來計算出所有父子節(jié)點的個數(shù)就為“?社交集群”的個數(shù), 接著根據(jù)題意排序即可: