1 条题解

  • 0
    @ 2020-05-09 14:16:09

    并查集,很简单

    • 操作 \(1\):查找两点连通性,find 函数,使用 f 数组记录
    • 操作 \(2\):连通两点,在 find 不连通下,使用 f 数组和 unionSet 函数合并
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int f[20086];
    
    void makeSet (int size) {
        for (int i = 1; i <= size; i++)
            f[i] = i;
        return;
    }
    
    int find (int x) {
        if (x != f[x]) 
            f[x] = find(f[x]);
        return f[x];
    }
    
    void unionSet (int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        f[x] = y;
    }
    
    int main () {
        int n, m;
        scanf("%d%d", &n, &m);
        makeSet(n);
        for (int i = 1; i <= m; i++) {
            int z, x, y;
            scanf("%d%d%d", &z, &x, &y);
            if (z == 1)
                unionSet(x, y);
            else 
                if (find(x) == find(y))
                    printf("Y\n");
                else 
                    printf("N\n");
        }
        return 0;
    }
    
    
  • 1

信息

ID
1006
难度
(无)
分类
并查集 点击显示
标签
递交数
1
已通过
0
通过率
0%
上传者