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

D - New Friends(AtCoder Beginner Contest 350)

题目链接:

D - New Friends (atcoder.jp)

题目大意:

题目解析:

 题目的大致意思: 假如A和B是朋友 B和C也是朋友 那么当A和C不是朋友的时候 可以通过B让A和C也成为朋友 问你增加了多少对的朋友关系

题目分析:

咱们可以从图论去考虑 当这一群是一个连通块 那么这一群点(人) 都是可以通过这个连通块去成为朋友的 那么假如这个连通块有N个人 那么就会有 N * (N - 1) / 2 条边(朋友关系)  那么全部的连通块减去之前的M条原有的朋友关系就是答案 注意开long 存取答案

那么问题来了 怎么去看他们是不是在一个连通块 并查集出手了

复习一下 并查集让点y到点x的连通下 那么就是p[find(y)] = find(x) 直接就过去了

代码:

import java.util.*;// 我认为这个题是并查集的题
public class D {public static int[] p = null; // 表示的是父亲public static void main(String[] args) {var sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();p = new int[n + 10];for(int i = 1; i <= n; i ++ ) {p[i] = i; // 刚开始的祖宗 都是自己自己}long ret = 0;int mm = m;var mp = new HashMap<Integer, Long>();var se = new TreeSet<Integer>();while(m -- != 0 ) {int x = sc.nextInt();int y = sc.nextInt();// 这里理解为y加到x的节点下面p[find(y)] = find(x); // 该不会是这里出问题了吧}for(int i = 1; i <= n; i ++ ) {int x = p[find(i)];if(!mp.containsKey(x)) {mp.put(x, 0l);}long t = mp.get(x) + 1;mp.put(x, t);se.add(x); // 这里面存的是 都是祖宗}for(int i : se) {//System.out.print("i = " + i + "\n");//System.out.print("x = " + mp.get(i) + "\n");long tt = mp.get(i);long t2 = mp.get(i) - 1;ret += tt * t2 / 2;//System.out.print("ret = " + ret + "\n");}ret -= mm;System.out.print(ret);}public static int find(int x) {if(x != p[x])p[x] = find(p[x]);return p[x];}
}

运行的结果:

 因为long问题和并查集认祖宗的问题 出现了几次wa

相关文章:

  • 海外仓快递系统哪个好?教你快速选到适合自己的管理系统
  • # linux 中使用 visudo 命令,怎么保存退出?
  • 【网络】高级IO(select||poll||epoll)
  • 中断处理过程介绍
  • 9. C++通过epoll+fork的方式实现高性能网络服务器
  • 前端面试题日常练-day37 【面试题】
  • 合并featurecount产生的多个表达矩阵文件
  • busco,checkM2:基因组或MAG完整度分析
  • Web开发——HTMLCSS
  • HTTP方法、状态码和请求过程
  • 安装 Android Studio 2024.1.1.6(Koala SDK35)和过程问题解决
  • Python开发 —— 错误ModuleNotFoundError: No module name
  • Java原生JDBC概览
  • 快速排序算法备考
  • [个人笔记] 记录CentOS7构建docker-ce的过程
  • Android单元测试 - 几个重要问题
  • Apache的80端口被占用以及访问时报错403
  • AWS实战 - 利用IAM对S3做访问控制
  • Java精华积累:初学者都应该搞懂的问题
  • js中的正则表达式入门
  • mysql常用命令汇总
  • niucms就是以城市为分割单位,在上面 小区/乡村/同城论坛+58+团购
  • oldjun 检测网站的经验
  • React Transition Group -- Transition 组件
  • Redis在Web项目中的应用与实践
  • 闭包--闭包作用之保存(一)
  • 基于遗传算法的优化问题求解
  • 开发了一款写作软件(OSX,Windows),附带Electron开发指南
  • 理清楚Vue的结构
  • 算法-插入排序
  • 腾讯视频格式如何转换成mp4 将下载的qlv文件转换成mp4的方法
  • 微信开放平台全网发布【失败】的几点排查方法
  • ​LeetCode解法汇总2182. 构造限制重复的字符串
  • (1)(1.9) MSP (version 4.2)
  • (C语言)深入理解指针2之野指针与传值与传址与assert断言
  • (function(){})()的分步解析
  • (附源码)ssm基于jsp的在线点餐系统 毕业设计 111016
  • (附源码)计算机毕业设计SSM疫情社区管理系统
  • (附源码)计算机毕业设计SSM在线影视购票系统
  • (机器学习-深度学习快速入门)第一章第一节:Python环境和数据分析
  • (入门自用)--C++--抽象类--多态原理--虚表--1020
  • (三)模仿学习-Action数据的模仿
  • (转)http-server应用
  • (转)IOS中获取各种文件的目录路径的方法
  • (转)Java socket中关闭IO流后,发生什么事?(以关闭输出流为例) .
  • (转)mysql使用Navicat 导出和导入数据库
  • . NET自动找可写目录
  • .apk文件,IIS不支持下载解决
  • .NET CF命令行调试器MDbg入门(一)
  • .net CHARTING图表控件下载地址
  • .NET 线程 Thread 进程 Process、线程池 pool、Invoke、begininvoke、异步回调
  • .NET开发人员必知的八个网站
  • .NET开源全面方便的第三方登录组件集合 - MrHuo.OAuth
  • .NET中使用Protobuffer 实现序列化和反序列化
  • .Net组件程序设计之线程、并发管理(一)