HiHo一下 Week14 并查集 + STL::map初探

HiHo

描述

输入

输出

样例

思路

简单的并查集，不过这里学了一下std::map的用法。啊啊啊啊这种stl的东西应该大一就开始学了。。为什么到现在还不会啊。。
map是一个C++的标准容器，提供的主要是一对一关系，比如，一个学生的姓名和他的学号。给出姓名要得到他的学号，如果开一个string数组来比较会很低效，map可以有效的解决这个问题。
在map里的一一对应我们叫做key-value 对于，也就是给出一个key,map可以返回value。

• 构造:
  比如上面的姓名学号可以用
  map<string,int>studentList;
  来构造(string 为key类型，int为value类型)。
• 添加
  我们要往里面加内容时可以用两种方式。
  一.
  studentList["张三"]=123;
  二.
  studentList.insert(pair<string,int>("江蛤",124));
• 查找
  先指定一个迭代器用来接收find()返回值。
  map<string,int>::iterator lIt;
  然后传入key值。
  lIt = studentList.find("张三");
  如果lIt = studentList.end()那么说明没有该数据，否则通过lIt->second可以获得该value值。
• 示例

map<string,int>stu;
stu["蛤蛤"]=123;
stu["嘻嘻"]=124;
map<string,int>::iterator lIt1;
lIt1 = stu.find("墨蛤");
if(lIt1== stu.end()) cout << "找不到蛤蛤";// 这里应该会输出  找不到蛤蛤
lIt1 = stu.find("嘻嘻");
cout << lIt1->second;   //这里应该会输出 124

map的使用中重要的是不要混淆了key和value。

代码

#include<iostream>
#include<map>
using namespace std;
int n;
std::map<string,int>peopleList;
int cla[100005];
int count=0;
int findCla(int a){
    int t=a;
    while(a!=cla[a]) a =cla[a];
    while(t!=cla[t]) {
        cla[t]=a;
        t=cla[t];
    }
    return a;
}
void unio(int a,int b){
    int aa = findCla(a);
    int bb = findCla(b);
    if(aa<bb)
        cla[bb]=aa;
    else 
        cla[aa]=bb;
}
int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        int model;
        string jia;
        string yi;
        cin >> model;
        cin >>jia;
        cin >>yi;
        if(!model){
            map<string,int>::iterator lIt1;
            lIt1 = peopleList.find(jia);
            map<string,int>::iterator lIt2;
            lIt2 = peopleList.find(yi);
            int x,y;
            if(lIt1 == peopleList.end()) {
                peopleList[jia] = count;
                x = count++;
                cla[x] = x;
            }else x = lIt1 -> second;
            if(lIt2 == peopleList.end()) {
                peopleList[yi] = count;
                y = count++;
                cla[y] = y;
            }else y = lIt2 -> second;
            unio(x,y);
        }else{
            map<string,int>::iterator lIt1;
            lIt1 = peopleList.find(jia);
            map<string,int>::iterator lIt2;
            lIt2 = peopleList.find(yi);
            int x,y;
            if(lIt1 == peopleList.end()) {
                peopleList[jia] = count;
                x = count++;
                cla[x] = x;
            }else x = lIt1 -> second;
            if(lIt2 == peopleList.end()) {
                peopleList[yi] = count;
                y = count++;
                cla[y] = y;
            }else y = lIt2 -> second;
            if(findCla(x)==findCla(y)) cout << "yes"<<endl;
                else cout << "no" << endl;
        }
    }
    return 0;
}