用并查集判断奇数环的C++代码

下面是使用并查集（Union Find）来判断奇数环的C++代码示例：

#include <iostream>
#include <vector>

using namespace std;

// 并查集的数据结构
class UnionFind {
public:
    vector<int> parent;
    vector<int> rank;
    
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        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];
    }
    
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

// 判断是否存在奇数环
bool hasOddCycle(vector<pair<int, int>>& edges, int n) {
    UnionFind uf(n + 1);
    
    for (auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        
        int rootU = uf.find(u);
        int rootV = uf.find(v);
        
        // 如果两个顶点属于同一个集合（有相同的根节点），则形成了一个偶数环
        if (rootU == rootV) {
            return false;
        }
        
        // 将两个顶点合并到同一个集合中
        uf.unite(u, v);
    }
    
    return true;
}

int main() {
    int n, m;
    cout << "请输入图的顶点数和边数：";
    cin >> n >> m;
    
    vector<pair<int, int>> edges;
    cout << "请输入每条边的起点和终点：" << endl;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges.push_back({u, v});
    }
    
    if (hasOddCycle(edges, n)) {
        cout << "该图没有奇数环" << endl;
    } else {
        cout << "该图存在奇数环" << endl;
    }
    
    return 0;
}

这段代码使用了并查集来判断图中是否存在奇数环。首先通过 `UnionFind` 类来实现并查集的数据结构，其中 `find` 函数用于查找顶点的根节点，`unite` 函数用于将两个顶点合并到同一个集合中。

然后，通过 `hasOddCycle` 函数来判断图中是否存在奇数环。它遍历所有的边，对于每条边的起点和终点，判断它们是否属于同一个集合。如果属于同一个集合，则说明形成了一个偶数环，返回 `false`。否则将两个顶点合并到同一个集合中。

最后，在 `main` 函数中输入图的顶点数和边数，以及每条边的起点和终点，然后调用 `hasOddCycle` 函数判断是否存在奇数环，并输出结果。