#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
private:
    vector<int> parent, rank, size;
    int components;
    
public:
    UnionFind(int n) : parent(n), rank(n, 0), size(n, 1), components(n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    // 带路径压缩的查找
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    
    // 按秩合并
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false; // 已经在同一集合中
        
        // 按秩合并：将较小的树连接到较大的树下
        if (rank[px] < rank[py]) {
            parent[px] = py;
            size[py] += size[px];
        } else if (rank[px] > rank[py]) {
            parent[py] = px;
            size[px] += size[py];
        } else {
            parent[py] = px;
            size[px] += size[py];
            rank[px]++;
        }
        
        components--;
        return true;
    }
    
    // 检查两个元素是否在同一集合中
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    
    // 获取包含x的集合大小
    int getSize(int x) {
        return size[find(x)];
    }
    
    // 获取连通分量数量
    int getComponents() {
        return components;
    }
};

int main() {
    cout << "并查集数据结构测试:" << endl;
    
    UnionFind uf(6);
    
    cout << "初始连通分量: " << uf.getComponents() << endl;
    
    // 连接一些元素
    uf.unite(0, 1);
    uf.unite(1, 2);
    uf.unite(3, 4);
    
    cout << "合并后: " << uf.getComponents() << " 个连通分量" << endl;
    
    // 测试连通性
    cout << "0和2连通: " << (uf.connected(0, 2) ? "是" : "否") << endl;
    cout << "0和3连通: " << (uf.connected(0, 3) ? "是" : "否") << endl;
    
    // 测试集合大小
    cout << "包含0的集合大小: " << uf.getSize(0) << endl;
    cout << "包含3的集合大小: " << uf.getSize(3) << endl;
    cout << "包含5的集合大小: " << uf.getSize(5) << endl;
    
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

class CycleDetector {
private:
    UnionFind uf;
    
public:
    CycleDetector(int n) : uf(n) {}
    
    bool hasCycle(vector<pair<int, int>>& edges) {
        for (auto& edge : edges) {
            int u = edge.first, v = edge.second;
            
            // 如果u和v已经连通，添加这条边会形成环
            if (uf.connected(u, v)) {
                return true;
            }
            
            // 连接u和v
            uf.unite(u, v);
        }
        return false;
    }
};

// 应用：Kruskal最小生成树算法
class KruskalMST {
private:
    struct Edge {
        int u, v, weight;
        bool operator<(const Edge& other) const {
            return weight < other.weight;
        }
    };
    
    vector<Edge> edges;
    int n;
    
public:
    KruskalMST(int vertices) : n(vertices) {}
    
    void addEdge(int u, int v, int w) {
        edges.push_back({u, v, w});
    }
    
    pair<int, vector<Edge>> findMST() {
        sort(edges.begin(), edges.end()); // 按权重排序
        UnionFind uf(n);
        
        vector<Edge> mst;
        int totalWeight = 0;
        
        for (const Edge& e : edges) {
            if (!uf.connected(e.u, e.v)) { // 不会形成环
                uf.unite(e.u, e.v);
                mst.push_back(e);
                totalWeight += e.weight;
                
                if (mst.size() == n - 1) break;
            }
        }
        
        return {totalWeight, mst};
    }
};

int main() {
    // 测试环检测
    cout << "环检测测试:" << endl;
    
    CycleDetector detector(4);
    vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {2, 3}, {3, 0}};
    
    if (detector.hasCycle(edges)) {
        cout << "图有环！" << endl;
    } else {
        cout << "图无环！" << endl;
    }
    
    // 测试Kruskal算法
    cout << "\nKruskal最小生成树测试:" << endl;
    
    KruskalMST kruskal(4);
    kruskal.addEdge(0, 1, 10);
    kruskal.addEdge(0, 2, 6);
    kruskal.addEdge(0, 3, 5);
    kruskal.addEdge(1, 3, 15);
    kruskal.addEdge(2, 3, 4);
    
    auto [weight, mst] = kruskal.findMST();
    cout << "MST权重: " << weight << endl;
    
    return 0;
}