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

图论第8天

685.冗余连接II

这题需要考虑两种情况:

1.两个输入

2.没有两个输入就是有成环

class Solution
{
public:static const int N = 1005;int father[N];int n;void init(){for (int i = 0; i <= n; i++){father[i] = i;}}int find(int x){return x == father[x] ? x : father[x] = find(father[x]);}int isSame(int a, int b){a = find(a);b = find(b);return (a == b);}void join(int a, int b){a = find(a);b = find(b);if (a == b)return;father[b] = a;}bool lianggeshuru(vector<vector<int>> &edges, int deleteNode){init();for (int i = 0; i < edges.size(); i++){if (i == deleteNode)continue;if (isSame(edges[i][0], edges[i][1])){return false;}join(edges[i][0], edges[i][1]);}return true;}vector<int> huan(vector<vector<int>> &edges){init();for (int i = 0; i < n; i++){if (isSame(edges[i][0], edges[i][1]))return edges[i];join(edges[i][0], edges[i][1]);}return {};}vector<int> findRedundantDirectedConnection(vector<vector<int>> &edges){n = edges.size();int count[N] = {0};// 有两个输入for (int i = 0; i < n; i++){count[edges[i][1]]++;}vector<int> vec;for (int i = n - 1; i >= 0; i--){if (count[edges[i][1]] == 2){vec.push_back(i);cout << i << endl;}}if (vec.size() > 0){if (lianggeshuru(edges, vec[0])){return edges[vec[0]];}else{return edges[vec[1]];}}// 有环return huan(edges);}
};

默写一遍再。其实突然就对这行代码不理解了,需要做个小实验。其实就是后面可以跟一个等式。

    int find(int x){return x == father[x] ? x : father[x] = find(father[x]);}

挺好挺好,默写出来啦!!!思路很重要!!!

class Solution {
public:static const int N = 1005;int father[N] = {0};void init(int num){for(int i = 0;i < num;i++){father[i] = i;}}int find(int x){return x == father[x] ? x : father[x] = find(father[x]);}bool isSame(int a,int b){a = find(a);b = find(b);return (a == b);}void join(int a ,int b){a = find(a);b = find(b);if(a == b)return;father[b] = a;}bool liashuru(vector<vector<int>>& edges,int deleteNode){init(edges.size());// because 1 <= ui, vi <= nfor(int i = 0;i< edges.size();i++){if(i == deleteNode)continue;if(isSame(edges[i][0],edges[i][1])){return false;}join(edges[i][0],edges[i][1]);}return true;}vector<int> huan(vector<vector<int>>& edges){init(edges.size());// because 1 <= ui, vi <= nfor(int i = 0;i < edges.size();i++){if(isSame(edges[i][0],edges[i][1])){return edges[i];}join(edges[i][0],edges[i][1]);}return {};}vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {int n = edges.size();int count[N] = {0};for(int i = 0;i < n;i++){count[edges[i][1]]++;}vector<int>vec;for(int i = n-1;i>=0;i--){if(count[edges[i][1]] == 2){vec.push_back(i);}}//俩输入if(vec.size() > 0){if(liashuru(edges,vec[0])){return edges[vec[0]];}else{return edges[vec[1]];}}//有环return huan(edges);}
};

那明天开始做面试题。

相关文章:

图论第8天

685.冗余连接II 这题需要考虑两种情况&#xff1a; 1.两个输入 2.没有两个输入就是有成环 class Solution { public:static const int N 1005;int father[N];int n;void init(){for (int i 0; i < n; i){father[i] i;}}int find(int x){return x father[x] ? x : f…...

Python怎么配置环境变量:深度探索与实战指南

Python怎么配置环境变量&#xff1a;深度探索与实战指南 在Python编程的世界中&#xff0c;环境变量的配置是一个至关重要的步骤。它不仅影响着Python解释器的运行&#xff0c;还关系到各种第三方库和工具的使用。本文将带你深度探索如何配置Python的环境变量&#xff0c;并为…...

计网期末复习指南(六):应用层(DNS、FTP、URL、HTTP、SMTP、POP3)

前言&#xff1a;本系列文章旨在通过TCP/IP协议簇自下而上的梳理大致的知识点&#xff0c;从计算机网络体系结构出发到应用层&#xff0c;每一个协议层通过一篇文章进行总结&#xff0c;本系列正在持续更新中... 计网期末复习指南&#xff08;一&#xff09;&#xff1a;计算…...

HTML做成一个炫酷跳动爱心的页面

大家好&#xff0c;今天制作制作一个炫酷跳动爱心的页面&#xff01; 先看具体效果&#xff1a; 要创建一个炫酷跳动爱心的HTML页面&#xff0c;你可以使用HTML、CSS和JavaScript的组合。以下是一个简单的示例&#xff0c;它使用CSS动画和JavaScript来实现跳动效果。 首先&…...

React + SpringBoot实现图片预览和视频在线播放,其中视频实现切片保存和分段播放

图片预览和视频在线播放 需求描述 实现播放视频的需求时&#xff0c;往往是前端直接加载一个mp4文件&#xff0c;这样做法在遇到视频文件较大时&#xff0c;容易造成卡顿&#xff0c;不能及时加载出来。我们可以将视频进行切片&#xff0c;然后分段加载。播放一点加载一点&am…...

Suse Linux ssh配置免密后仍需要输入密码

【问题描述】 Suse Linux已经配置了ssh免密&#xff0c;但无法ssh到目标服务器。 对自身的ssh登陆也需要输入密码。 系统–Suse 15 SP5 【重现步骤】 1.使用ssh-keygen -t rsa生产key文件 2.使用ssh-copy-id拷贝public key到目标机器(或者自身) 3.配置成功后ssh 目标时仍需要输…...

apifox 生成签名

目录 前言准备编写签名脚本签名说明捋清思路编码获取签名所需的参数生成签名将签名放到合适的位置完整代码 在apifox中配置脚本新增公共脚本引用公共脚本添加环境变量 参考 前言 略 准备 查看apifox提供的最佳实践文章&#xff1a;接口签名如何处理 编写签名脚本 签名说明…...

介绍建造者模式

建造者模式 将一个复杂对象的创建与它的表示分离&#xff0c;使得同样的构建过程可以创建不同的表示 四种角色 Product 产品角色 指的是一个具体的产品对象Builder 抽象建造者 创建一个产品对象的各个部件的接口/抽象类ConcreteBuilder 具体建造者 实现或继承抽象建造者接口…...

【全部更新完毕】2024全国大学生数据统计与分析竞赛B题思路代码文章教学数学建模-电信银行卡诈骗的数据分析

电信银行卡诈骗的数据分析 摘要 电信银行卡诈骗是当前社会中严重的犯罪问题&#xff0c;分析电信银行卡交易数据&#xff0c;找出高风险交易特征&#xff0c;建立预测模型&#xff0c;将有助于公安部门和金融机构更好地防范诈骗行为&#xff0c;保障用户的财产安全。 针对问…...

【应用浅谈】Odoo的库存计价与产品成本(三)

序言:时间是我们最宝贵的财富,珍惜手上的每个时分 Odoo的库存&#xff08;Stock&#xff09;模块拥有众多功能&#xff0c;其中库存计价是一项非常重要的功能&#xff0c;原生的成本方法分三种&#xff1a;【标准成本】&#xff0c;【平均成本】&#xff0c;【先进先出】&#…...

数据结构之ArrayList与顺序表(下)

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a;数据结构&#xff08;Java版&#xff09; 目录 ArrayList的具体使用 118. 杨辉三角 扑克洗牌算法 接上篇&#xff1a;数据结构之ArrayLis…...

openi启智社区 aarch64 npu环境安装飞桨paddlepaddle和PaddleNLP(失败)

以前在启智社区都是编译安装飞桨&#xff0c;这回看到飞桨提供了npu安装包&#xff0c;兴冲冲的以为安装很简单。 之所以安装飞桨&#xff0c;是因为想在启智社区的启智大脑调试环境使用最新的PaddleNLP&#xff0c;结果报错&#xff1a;No module named paddle.nn.layer.laye…...

【漏洞复现】多客圈子论坛系统 httpGet 任意文件读取漏洞

0x01 产品简介 多客圈子论坛系统是一种面向特定人群或特定话题的社交网络&#xff0c;它提供了用户之间交流、分享、讨论的平台。在这个系统中&#xff0c;用户可以创建、加入不同的圈子&#xff0c;圈子可以是基于兴趣、地域、职业等不同主题的。用户可以在圈子中发帖、评论、…...

46-1 护网溯源 - 钓鱼邮件溯源

一、客户提供钓鱼邮件样本 二、行为分析 三、样本分析 对钓鱼邮件中的木马程序1111.exe文件进行了分析,提交了360安全大脑沙箱云和微步在线云沙箱。 360安全大脑沙箱云显示,该1111.exe文件存在危险,因此在解压时需要谨慎操作,以免触发木马程序。 建议使用360压缩软件进行…...

鸿蒙低代码开发一个高频问题

在版本是DevEco Studio 3.1.1 Release&#xff0c;SDK是3.1.0(API9)。 创建和设计的visual文件经常会遇到无法渲染的情况&#xff0c;或者自定义组件在Custom列表中突然不见了的情况。 有以下报错信息的&#xff1a; JSON schema validation error: data/visualModel/value/…...

关于使用南墙waf防护halo网站主页请求404报错的解决方案

文章目录 环境说明问题展示原因探究解决方法 环境说明 在1panel应用商店&#xff0c;部署南墙waf(docker版)halo(2.16.1社区版)注意部署过程中注意uuwaf必须勾选允许外部访问&#xff0c;halo可以不勾选[这里为了证明确实是南墙waf的原因&#xff0c;选择勾选] 问题展示 使…...

Elasticsearch 认证模拟题 - 13

一、题目 集群中有索引 task3&#xff0c;用 oa、OA、Oa、oA 查询结构是 4 条&#xff0c;使用 dingding 的查询结果是 1 条。通过 reindex 索引 task3 为 task3_new&#xff0c;能够使 task3_new 满足以下查询条件。 使用 oa、OA、Oa、oA、0A、dingding 查询都能够返回 6 条…...

Day25 首页待办事项及备忘录添加功能

​ 本章节,完成首页待办事项及备忘录添加功能 一.修改待办事项和备忘录逻辑处理类,即AddMemoViewModel和AddTodoViewModel 在 AddMemoViewModel逻辑处理类中,为了支持与其关联的View视图文件的数据绑定,需要定义一个与视图文件相匹配的实体类 Model。这个Model将包含 View中…...

SpringBoot——全局异常处理

目录 异常 项目总结 新建一个SpringBoot项目 pom.xml Result&#xff08;通用的响应结果类&#xff09; MyBusinessException自定义异常类 GlobalExceptionHandler全局异常处理类 ExceptionController控制器 SpringbootExceptionApplication启动类 参考文章&#xff1a…...

SpringBoot+Vue教师工作量管理系统(前后端分离)

技术栈 JavaSpringBootMavenMySQLMyBatisVueShiroElement-UI 角色对应功能 教师管理员 功能截图...

别再只盯着机械式了!一文看懂MEMS、Flash、OPA等固态激光雷达怎么选(附避坑指南)

固态激光雷达技术全景&#xff1a;从MEMS到OPA的实战选型策略 激光雷达技术正在经历一场静默革命——机械旋转部件逐渐被半导体芯片取代&#xff0c;就像当年电子管被晶体管淘汰的历史重演。在自动驾驶和机器人领域摸爬滚打多年的工程师都清楚&#xff0c;选择激光雷达就像在迷…...

Cesium三维地形剖切与开挖:从原理到可复用组件封装

1. 为什么需要地形剖切与开挖功能&#xff1f; 在三维地理信息系统中&#xff0c;地形剖切与开挖是最常用的分析功能之一。想象一下&#xff0c;你正在规划一条地下隧道&#xff0c;或者需要分析某处地质构造&#xff0c;这时候如果能把地表"切开"查看内部情况&#…...

性价比好的深圳除甲醛公司

深圳作为高密度开发城市&#xff0c;常年保持稳定的新房交付、写字楼翻新与商铺装修需求&#xff0c;装修带来的甲醛残留问题&#xff0c;始终是业主和企业管理者关注的室内安全重点。目前深圳本地已有大量除甲醛服务机构&#xff0c;消费者可根据自身需求筛选适配的服务主体。…...

别再死磕动态规划了!用Python模拟退火算法搞定背包问题,附完整代码

用Python模拟退火算法优雅解决背包问题&#xff1a;从理论到实战 在算法学习的过程中&#xff0c;背包问题就像一座难以逾越的高山&#xff0c;让无数初学者望而生畏。传统的动态规划解法虽然精确&#xff0c;但代码实现复杂、状态转移方程难以理解&#xff0c;对于实际应用场景…...

CTF新手必看:用010Editor和CRC校验,5分钟揪出被篡改的PNG图片宽高

CTF新手实战&#xff1a;5分钟掌握PNG图片宽高篡改检测技巧 当你第一次参加CTF比赛&#xff0c;面对一张无法正常显示的PNG图片时&#xff0c;是否感到无从下手&#xff1f;这很可能是题目设计者修改了图片的宽高参数。作为MISC方向的基础题型&#xff0c;掌握快速检测PNG图片…...

终极指南:League-Toolkit 如何彻底解决极地大乱斗抢英雄难题

终极指南&#xff1a;League-Toolkit 如何彻底解决极地大乱斗抢英雄难题 【免费下载链接】League-Toolkit An all-in-one toolkit for LeagueClient. Gathering power &#x1f680;. 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit League-Toolkit 是一款…...

Obsidian-Zettelkasten终极指南:20+模板构建你的第二大脑

Obsidian-Zettelkasten终极指南&#xff1a;20模板构建你的第二大脑 【免费下载链接】Obsidian-Templates A repository containing templates and scripts for #Obsidian to support the #Zettelkasten method for note-taking. 项目地址: https://gitcode.com/gh_mirrors/o…...

RT-DTER最新创新改进系列:(购买资料的粉丝反馈涨点的TOP1模块)我们将BiFPN的加权双向融合之力,注入RT-DETR的端到端Transformer架构,创新与涨点的双丰收!!!!!!

RT-DTER最新创新改进系列&#xff1a;&#xff08;购买资料的粉丝反馈涨点的TOP1模块&#xff09;我们将BiFPN的加权双向融合之力&#xff0c;注入RT-DETR的端到端Transformer架构&#xff0c;创新与涨点的双丰收&#xff01;&#xff01; 购买相关资料后畅享一对一答疑&#…...

AI Agent + 指纹浏览器:从0搭建MCP Server实现批量账号自动化管理

我是张大鹏&#xff0c;做了十多年人工智能&#xff0c;带过不少项目。说实话&#xff0c;AI Agent 最难的不是生成内容&#xff0c;是"动手干活"——大模型再强&#xff0c;如果只能输出文字而不能操控真实环境&#xff0c;自动化就永远差最后一公里。最近在研究 In…...

淘宝淘金币自动化脚本终极指南:每天节省20分钟的完整解决方案

淘宝淘金币自动化脚本终极指南&#xff1a;每天节省20分钟的完整解决方案 【免费下载链接】taojinbi 淘宝淘金币自动执行脚本&#xff0c;包含蚂蚁森林收取能量&#xff0c;芭芭农场全任务&#xff0c;解放你的双手 项目地址: https://gitcode.com/gh_mirrors/ta/taojinbi …...