文章

231

粉丝

165

获赞

376

访问

114.6k

头像
graph's connected components(弱化版) 题解:
P1687 中南大学机试题
发布于2026年3月18日 18:49
阅读数 133

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

int find(vector<int>& parent, int x) {
    // 非递归路径压缩
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    // 路径压缩
    while (x != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

void unite(vector<int>& parent, int x, int y) {
    int rx = find(parent, x);
    int ry = find(parent, y);
    if (rx != ry) {
        parent[ry] = rx; // 简单合并
    }
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<int> a(m);
        for (int i = 0; i < m; ++i) {
            cin >> a[i];
        }
        vector<int> parent(m);
        for (int i = 0; i < m; ++i) parent[i] = i;

        // 枚举所有点对
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                if ((a[i] & a[...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发