#pragma once

#include <iostream>
#include <vector>
#include <map>

namespace Lenyiin
{
    class UnionFindSet
    {
    public:
        // 初始化: 为每个元素单独分配一个集合, 初始时每个集合大小为 1, 用 -1 表示
        UnionFindSet(int n)
            : _v(n, -1) // 初始化所有元素都为根节点, 且集合大小为1
        {
        }

        // 查找操作: 找到元素 x 所属集合的根节点, 并使用路径压缩优化
        int FindRoot(int x)
        {
            int root = x;
            // 查找根节点, 沿着父节点链向上寻找
            while (_v[root] >= 0)
            {
                root = _v[root];
            }

            // 路径压缩: 将路径上所有节点直接挂在根节点下
            while (x != root)
            {
                int parent = _v[x]; // 保存当前节点的父节点
                _v[x] = root;       // 将当前节点直接连接到根节点
                x = parent;         // 继续处理父节点
            }

            return root; // 返回根节点
        }

        // 合并两个集合: 使用按秩合并优化
        bool Union(int x1, int x2)
        {
            int root1 = FindRoot(x1);
            int root2 = FindRoot(x2);

            // 如果本身就在一个集合里, 则无需合并
            if (root1 == root2)
            {
                return false;
            }

            // 按秩合并: 始终将较小的集合挂到较大的集合上
            if (_v[root1] < _v[root2]) // root1 集合规模较大（负值越小, 集合越大）
            {
                _v[root1] += _v[root2]; // 增加 root1 集合的大小
                _v[root2] = root1;      // root2 挂到 root1 上
            }
            else
            {
                _v[root2] += _v[root1]; // 增加 root2 集合的大小
                _v[root1] = root2;      // root1 挂到 root2 上
            }

            return true; // 合并成功
        }

        // 判断两个元素是否在同一个集合中
        bool InSet(int x1, int x2)
        {
            return FindRoot(x2) == FindRoot(x2);
        }

        // 统计当前集合的个数
        size_t SetSize()
        {
            size_t count = 0;
            for (auto e : _v)
            {
                if (e < 0) // 只有根节点存储负值, 表示集合的大小
                {
                    ++count;
                }
            }
            return count;
        }

        // 打印当前并查集的结构 (用于调试)
        void Print() const
        {
            for (int i = 0; i < _v.size(); ++i)
            {
                printf("v[%d] == %d\n", i, _v[i]);
            }
            printf("\n");
        }

    private:
        std::vector<int> _v; // 存储每个元素的父节点或集合大小
    };
}

// namespace Lenyiin
//{
//	template <class T>
//	class UnionFindSet
//	{
//	public:
//		UnionFindSet(const T* a, size_t n)
//		{
//			for (size_t i = 0; i < n; ++i)
//			{
//				_v.push_back(a[i]);
//				_indexmap[a[i]] = i;
//			}
//		}
//
//	private:
//		vector<T> _v;			// 人找编号
//		map<T, int> _indexmap;	// 编号找人
//	};
// }