#include<iostream>
const int SIZE = 9;
int parent[SIZE];
// 非递归版查询x的根节点
int find(int x)
{
    while(x != parent[x])
    {
        x = parent[x];
    }
    return x;
}
// 递归版查询x的根节点
int r_find(int x)
{
    if(x == parent[x]) return x;
    return r_find(parent[x]);
}
// 合并x和y
void merge(int x, int y)
{
    int x_root = find(x);
    int y_root = find(y);
    if (x_root != y_root)
    {
        parent[y_root] = x_root;
    }
}
int main()
{
    for(int i = 1; i < SIZE; ++i)
    {
        parent[i] = i;
    }
    int x, y;
    // 输入6组两个整数，全都合并。
    for(int i = 1; i <= 6; ++i)
    {
        std::cin >> x >> y;
        merge(x, y);
    }
    for(int i = 1; i < SIZE; ++i)
    {
        std::cout << parent[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "输入要查询的2个元素是否在一个集合：";
    std::cin >> x >> y;
    std::cout << (find(x) == find(y) ? "在" : "不在") << std::endl;
}

#include<iostream>
#include<vector>
#include<ctime>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int main()
{
    vector<int> vec;
    srand(time(NULL));
    for(int i = 0; i < 1000; ++i)
    {
        vec.push_back(rand() % 100);
    }
    // 问题1：找第一个出现重复的数字 - 需要set来统计
    unordered_set<int> set1;
    int count = 0;
    for(const auto & key : vec)
    {
        const auto it = set1.find(key); // O(1)
        if (it == set1.end())
        {
            set1.insert(key);
        }
        else
        {
            cout << "重复的数字是" << key << endl;
            ++count;
            // break; // 找所有重复出现的数字时，去掉break
        }
    }
    std::cout << "总共重复了" << count << "个数" << endl;
    // 问题2：统计重复的数字以及出现的次数 - 需要map来统计数字及次数
    unordered_map<int, int> map1;
    for(const auto & key : vec)
    {
        const auto it = map1.find(key);   // O(1)
        if (it == map1.end()) 
        {
            // map插入的是pair，这里emplace可以直接构建
            map1.emplace(key, 1); // O(1)
        }
        else
        {
            ++it->second;
        }
        // 以上for区域中的语句可以被一行代码代替：++map1[key]
    }
    for(const auto & pair : map1)
    {
        if(pair.second > 1)
        {
            cout << "数字" << pair.first << "重复" << pair.second << "次" << endl;
        }
    }
    // 问题3：去重
    unordered_set<int> set2;
    for(const auto & key : vec)
    {
        set2.emplace(key);
    }
    // 问题4：字符串中找第一个没有重复出现过的字符
    bool haveDuplicate = false;
    string str = "fgodgnffinogiofdngps";
    unordered_map<char, int> map2;
    for(const auto & key : str)
    {
        ++map2[key];
    }
    for(const auto & key : str)
    {
        if (map2[key] == 1)
        {
            haveDuplicate = true;
            cout << "第一个不重复的字符为" << key << endl;
            break;
        }
    }
    if (!haveDuplicate)
    {
        cout << "所有字符都重复" << endl;
    }
}