/*
*?? ?題目描述：
?? ??? ?幼兒園老師安排小朋友做游戲，現在需要給N個小朋友進行分組，老師讓每個同學寫一個名字，代表這位小朋友
?? ??? ?想和誰分到一組，請問老師在滿足所有小朋友意愿的情況下，最多可以將班級分成多少組？
?? ?輸入描述：
?? ??? ?第一行輸入N，0<N<=100000
?? ??? ?接下來的N行代表每個小朋友希望和誰分到一組，如“John Jack”，代表John希望和Jack分到一組，兩個名字之間
?? ??? ?以空格分割，名字本身不存在空格
?? ?輸出描述：
?? ??? ?分組的最多數量

? ? ?示例：

? ? ? ? 輸入：

? ? ? ? 3

? ? ? ? Tom John

? ? ? ? John Jane

? ? ? ? Jane Tom

? ? ? ? 輸出：

? ? ? ? 1

*?? ?

---

說明：華為0407第一題

考察知識點：并查集

---

解題思路：

? ? ? ? 1、使用hash表建立每個小朋友的父節點關系表；

? ? ? ? 2、輸出有幾個連通圖

---

代碼如下：

#include<iostream> #include<unordered_map> #include<string> using namespace std; class UF { private:unordered_map<string, string> fri;//vector<string> fri;int circle; public:UF(int person_num) {circle = person_num;}void add(string s) {//fri.push_back(s);if (fri.find(s) == fri.end()) fri[s] = "";}string find(string s) {if (fri[s] == "") return s;string root = s;while (fri[root] != "") {root = fri[root];}string pre_father;while (root != s) {pre_father = fri[s];fri[s] = root;s = pre_father;}return root;}void connect(string s1, string s2) {if (find(s1) == find(s2)) return;string root_1 = find(s1);string root_2 = find(s2);fri[root_1] = root_2;circle--;}int getCircle() {return circle;} };int main() {int N;cin >> N;string f1, f2;UF uf(N);for (int i = 0; i < N; ++i) {// john jackcin >> f1 >> f2;uf.add(f1);uf.add(f2);uf.connect(f1, f2);}cout << uf.getCircle() << endl; }

總結

以上是生活随笔為你收集整理的【秋招机试真题】华为机试0407-1-幼儿园小朋友分组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。