PTA 1034 Head of a Gang C++

　　题目来源：https://pintia.cn/problem-sets/994805342720868352/problems/994805456881434624
　　由于之前在学习数据结构和算法时，学校禁止使用C++ STL，所以现在刷算法时STL中很多趁手武器不会用，惭愧...
　　本题重点之一是映射，需要使用map数据结构
　　

1. #include <map>
2. using namespace std;
4. map<int, string> m;

复制代码

　　由此可以完成从 int类型的键到 string类型的值的 一对多映射
　　插入操作使用重载的运算符[]，在插入之前，先在map中查询一下是否有已经存在

1. // idNumber是全局变量，初值为0<br>int Mapping(string s) {
2.     int ret = -1;
3.     if (s2i.count(s) == 0) {　　//完成 string<->int 一一映射，如 "AAA"<-> 0
4.         s2i[s] = idNumber;
5.         i2s[idNumber] = s;
6.         ret = idNumber;
7.         idNumber++;
8.     } else
9.         ret = s2i[s];
10.     return ret;
11. }

复制代码

　　第二部分，整理一下结构体数组的排序

1. struct Node  {
2.     string s;
3.     int n;
4. };
5. bool cmp(Node a, Node b) {
6.     return a.s < b.s;　　//按照string变量非降序排序，如果是想按Node中n排序同理
7. }
9. // 如果是结构体数组=>Node a[size];
10. sort(a, a + size, cmp);
11. // 如果是vector<Node> v
12. sort(v.begin(), v.end(), cmp);

复制代码

 
　　其他均为正常图论算法，主要涉及对联通分量的处理，略。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！