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

Day56 图论part06

108.冗余连接

并查集应用类题目,关键是如何把题意转化成并查集问题

代码随想录

import java.util.Scanner;

public class Main{
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        DisJoint disjoint = new DisJoint(n+1);
        
        while(n-- > 0){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            if(disjoint.isSame(a, b)){
                System.out.println(a+" "+b);
                break;
            }else{
               disjoint.join(a, b); 
            }
        }
    }
}

class DisJoint{
    private int[] farther;
    
    public DisJoint(int N){
        farther = new int[N];
        for(int i = 0; i < N; i++){
            farther[i] = i;
        }
    }
    
    public int find(int n){
        if(n == farther[n]){
            return n;
        }else{
            return farther[n] = find(farther[n]);
        }
       // return n == farther[n] ? n : (farther[n] = find(farther[n]));
    }
    
 

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

相关文章:

  • 复习打卡大数据篇——Hadoop MapReduce
  • QT线程 QtConcurrent (深入理解)
  • Vue中动态样式绑定+CSS变量实现切换明暗主题功能——从入门到进阶
  • 04软件测试需求分析案例-用户登录
  • 如何从 0 到 1 ,打造全新一代分布式数据架构
  • 基于YOLOV5+Flask安全帽RTSP视频流实时目标检测
  • .net core 的多线程编程
  • stm32f103zet6 i2c 四针 oled 标准库开发
  • 机试题——圣诞节礼盒
  • python监控数据处理应用服务Socket心跳解决方案
  • 树莓集团:解读资源整合是什么意思?
  • C语言基础学习记录-文件管理
  • RabbitMQ工作模式(详解 工作模式:简单队列、工作队列、公平分发以及消息应答和消息持久化)
  • Zettlr(科研笔记) v3.4.1 中文版
  • 在Nginx部署Web应用,如何保障后端API的安全
  • 找到字符串中所有字母异位词
  • 云原生大数据计算服务 MaxCompute
  • IPv6的报头
  • 全视通智慧机构养老方案,含有紧急呼叫、安全保障等系统
  • Lua元方法
  • element-ui表格多级表头固定列和合并单元格
  • HTML CSS 超链
  • TCP 传输可靠性保障
  • 7-6 最小生成树-prim
  • HTTPS验证流程
  • 地理数据库Telepg面试内容整理-在Telepg数据库中,如何进行空间数据的存储与管理