当前位置: 首页 > article >正文

19873连通块中点的数量

19873连通块中点的数量

⭐️难度:中等
🌟考点:连通块、并查集
📖
在这里插入图片描述

📚

package test;

import java.util.Scanner;

public class Main {
    static int N = 100010;
    static int[] a = new int[N];
    static int[] p = new int[N];
    static int[] size = new int[N];
    static int n;
    static int m;

    // 路径优化
    static int find(int x) {
        return p[x] == x ? x : (p[x] = find(p[x]));
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        // 初始化并查集
        for (int i = 1; i <= n; i++) {
            a[i] = i;
            p[i] = i; // 每个点的父节点初始化为自身
            size[i] = 1;
        }

        for (int i = 1; i <= m; i++) {
            String op = sc.next();
            if (op.equals("C")) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                int px = find(x);
                int py = find(y);
                if (px != py) {
                    size[py] += size[px]; // 先更新 size 数组
                    p[px] = py; // 再合并
                }
            } else if (op.equals("Q1")) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                if (find(x) == find(y)) {
                    System.out.println("Yes");
                } else {
                    System.out.println("No");
                }
            } else {
                int x = sc.nextInt();
                System.out.println(size[find(x)]);
            }
        }
    }
}

http://www.kler.cn/a/583717.html

相关文章:

  • 回归预测 | MATLAB实现SSA-LSTM和LSTM多输入单输出
  • Git 的基本概念和使用方式(附有思维导图)
  • 一维下料之 *贪心算法* —— CAD c#二次开发
  • 【软考-架构】3.3、模式分解-事务并发-封锁协议
  • C# WPF 基础知识学习(一)
  • 贪心算法(5)(java)k次取反后最大化的数组和
  • 什么是AI?AI能对我们生活产生哪些影响?
  • LeetCode 112. 路径总和 II java题解
  • 如何用Docker容器化Java应用?Spring Boot实战指南
  • Spring Boot 约定大于配置:实现自定义配置
  • HCIP复习拓扑练习(修改版)
  • 【3DGS】SuperSplat本地运行+修改监听端口+导入ply模型+修剪模型+在线渲染3DGS网站推荐
  • 设计模式C++
  • Java 8新特性:Lambda表达式与Stream API实战
  • OEM SQL Details and Session Details 5s 或者parallel 才会在sql monitor显示
  • Aliyun CTF 2025 web 复现
  • uniapp,自绘仪表盘组件(基础篇)
  • BEVDepth: Acquisition of Reliable Depth for Multi-view 3D Object Detection 论文阅读
  • c# txt文档的实时显示,用来查看发送接收指令
  • 如何简单获取三个月免费试用的SSL证书