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

【代码随想录Day54】图论Part06

冗余连接

题目链接/文章讲解:代码随想录

import java.util.Scanner;

public class Main {
    private int numberOfNodes; // 节点数量
    private int[] parent; // 存储每个节点的父节点

    // 构造函数初始化并查集
    public Main(int size) {
        numberOfNodes = size;
        parent = new int[size + 1]; // 根据节点数量初始化数组
        initializeUnionFind();
    }

    // 初始化并查集,将每个节点的父节点设为自身
    private void initializeUnionFind() {
        for (int i = 0; i <= numberOfNodes; i++) {
            parent[i] = i;
        }
    }

    // 查找节点node的根节点,并进行路径压缩
    private int find(int node) {
        if (node == parent[node]) {
            return node;
        }
        // 路径压缩
        parent[node] = find(parent[node]);
        return parent[node];
    }

    // 判断节点nodeU和节点nodeV是否属于同一集合
    public boolean isSameSet(int nodeU, int nodeV) {
        return find(nodeU) == find(nodeV);
    }

    // 将节点nodeV连接到节点nodeU
    public void union(int nodeU, int nodeV) {
        int rootU = find(nodeU); // 寻找nodeU的根
        int rootV = find(nodeV); // 寻找nodeV的根
        if (rootU != rootV) {
            parent[rootV] = rootU; // 将nodeV的根节点设为nodeU的根节点
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numberOfEdges = scanner.nextInt(); // 输入边的数量
        Main unionFind = new Main(numberOfEdges); // 初始化并查集

        for (int i = 0; i < numberOfEdges; i++) {
            int nodeU = scanner.nextInt(); // 输入节点U
            int nodeV = scanner.nextInt(); // 输入节点V
            if (unionFind.isSameSet(nodeU, nodeV)) {
                System.out.println(nodeU + " " + nodeV); // 如果nodeU和nodeV已连接,输出并结束
                return;
            } else {
                unionFind.union(nodeU, nodeV); // 否则将nodeU和nodeV连接
            }
        }
        scanner.close(); // 关闭扫描器
    }
}

冗余连接 II

题目链接/文章讲解:代码随想录

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static int numberOfNodes;
    private static int[] parent;

    // 并查集初始化
    private static void initializeUnionFind() {
        for (int i = 1; i <= numberOfNodes; i++) {
            parent[i] = i;
        }
    }

    // 并查集里寻根的过程
    private static int find(int node) {
        if (node != parent[node]) {
            parent[node] = find(parent[node]); // 路径压缩
        }
        return parent[node];
    }

    // 将边 v -> u 加入并查集
    private static void union(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            parent[rootV] = rootU; // 将 v 的根指向 u 的根
        }
    }

    // 判断 u 和 v 是否找到同一个根
    private static boolean areInSameComponent(int u, int v) {
        return find(u) == find(v);
    }

    // 在有向图里找到删除的那条边,使其变成树
    private static void findEdgeToRemove(List<int[]> edges) {
        initializeUnionFind(); // 初始化并查集
        for (int i = 0; i < edges.size(); i++) { // 遍历所有的边
            int[] edge = edges.get(i);
            if (areInSameComponent(edge[0], edge[1])) { // 构成有向环了,就是要删除的边
                System.out.println(edge[0] + " " + edge[1]);
                return;
            } else {
                union(edge[0], edge[1]);
            }
        }
    }

    // 删一条边之后判断是不是树
    private static boolean isTreeAfterRemovingEdge(List<int[]> edges, int edgeToRemoveIndex) {
        initializeUnionFind(); // 初始化并查集
        for (int i = 0; i < edges.size(); i++) {
            if (i == edgeToRemoveIndex) continue; // 跳过要删除的边
            int[] edge = edges.get(i);
            if (areInSameComponent(edge[0], edge[1])) { // 构成有向环了,一定不是树
                return false;
            }
            union(edge[0], edge[1]);
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        numberOfNodes = scanner.nextInt();
        parent = new int[numberOfNodes + 1];
        List<int[]> edges = new ArrayList<>();
        int[] inDegree = new int[numberOfNodes + 1]; // 记录节点入度

        for (int i = 0; i < numberOfNodes; i++) {
            int startNode = scanner.nextInt();
            int endNode = scanner.nextInt();
            inDegree[endNode]++;
            edges.add(new int[]{startNode, endNode});
        }

        List<Integer> edgeIndicesWithInDegreeTwo = new ArrayList<>(); // 记录入度为2的边索引
        // 找入度为2的节点所对应的边,注意要倒序,因为优先删除最后出现的一条边
        for (int i = numberOfNodes - 1; i >= 0; i--) {
            if (inDegree[edges.get(i)[1]] == 2) {
                edgeIndicesWithInDegreeTwo.add(i);
            }
        }

        // 情况一、情况二
        if (!edgeIndicesWithInDegreeTwo.isEmpty()) {
            // 放在 edgeIndicesWithInDegreeTwo 里的边已经按照倒叙放的,所以这里就优先删第一个
            if (isTreeAfterRemovingEdge(edges, edgeIndicesWithInDegreeTwo.get(0))) {
                System.out.println(edges.get(edgeIndicesWithInDegreeTwo.get(0))[0] + " " + edges.get(edgeIndicesWithInDegreeTwo.get(0))[1]);
            } else {
                System.out.println(edges.get(edgeIndicesWithInDegreeTwo.get(1))[0] + " " + edges.get(edgeIndicesWithInDegreeTwo.get(1))[1]);
            }
            return;
        }

        // 处理情况三
        // 明确没有入度为2的情况,那么一定有有向环,找到构成环的边返回
        findEdgeToRemove(edges);
    }
}

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

相关文章:

  • 多语言多商家版线上购物商城/在线客服/商家入驻/代理后台/全开源跨境电子商务系统
  • Python大数据可视化:基于python大数据的电脑硬件推荐系统_flask+Hadoop+spider
  • Wend看源码-Java-集合学习(Set)
  • 一种寻路的应用
  • “游戏信息化”:游戏后台系统的未来发展
  • uniapp实现APP、小程序与webview页面间通讯
  • 鸿蒙OS:中国智造的基石
  • w012基于springboot的社区团购系统设计
  • hadoop_yarn-site.xml
  • Chrome和夸克谁更护眼
  • OpenCV视觉分析之目标跟踪(2)卡尔曼滤波器KalmanFilter的使用
  • 【React】createContext 和 useContext
  • IDEA:ctrl+/ 快捷键生成的注释,设置“//”开始位置
  • 【机器学习】二分类神经网络
  • 摄像机实时接入分析平台LiteAIServer视频智能分析软件视频诊断中的抖动检测功能
  • 【99.9%解决】vue3+vite+typescript+vscode使用@alias路径别名配置不正确导致红色波浪线的解决办法
  • ssm026校园美食交流系统+vue(论文+源码)_kaic
  • 第三百零六节 Log4j教程 - Log4j日志级别
  • kubevirt cloud-init配置
  • 【解决方案】用git reset --hard重置了提交但是发现reset了一些本不该reset的内容,是不是寄了?
  • Android 圆形进度条CircleProgressView 基础版
  • Linux 程序地址空间
  • python读取视频并转换成gif图片
  • Python爬虫之urllib库详解
  • 【论文阅读笔记】VLP: A Survey on Vision-language Pre-training
  • 基于AI深度学习的中医针灸实训室腹针穴位智能辅助定位系统开发