首页 > 其他分享 >构造加逊

构造加逊

时间:2023-04-16 21:47:10浏览次数:37  
标签:度数 连通 联通 加逊 构造 答案 操作

  1. Make It Connect
  • 题意

    给定一个无向图 \(E\) ,每次操作需要选择一个点 \(u\) ,然后对其余的的所有点 \(v\) 进行操作,如果 \((u, v)\in E\) 则删去这条边,否则将这条边加入图中,求最少几次类似操作能够使得图联通并输出操作方案

  • 做法

    首先统计联通块数量以及各点的度数

    • 当原图为连通图时,答案显然为 \(0\) 。

    • 当图中存在一个度数为 \(0\) 的点,答案显然为 \(1\) 。

    • 当存在一个连通块不是团时,答案也为 \(1\) 。

      在该连通块中找到任意一个度数小于该连通块大小减一的非割点,并对其进行操作。因为不是团,因此在操作后依然保证原有连通块的联通,且能与其他连通块连边,固操作正确性有保障。

    • 当存在三个及以上的连通块时,答案为 \(2\) 。

      第一步为任选一个点进行操作,此时连通块的数量显然为会变成 \(2\) ,并且其中一定有一个连通块不是团,此时即为上一种情况,不再赘述。

    • 最后一种情况,两个连通块均为团,答案为较小连通块的大小。

      对小连通块中每个点均进行操作,正确性不难证明。

标签:度数,连通,联通,加逊,构造,答案,操作
From: https://www.cnblogs.com/Jadebo1/p/17324165.html

相关文章

  • 算法-二叉树的构造
    namespaceBinary;publicclassBinaryTree{publicNode<char>Head{get;privateset;}privatestringcStr{get;set;}publicBinaryTree(stringconstructStr){this.cStr=constructStr;th......
  • 利用AntDesign中a-tree和checkbox构造组织单位人员树选择组件
    业务效果图核心代码<template><divclass="select-container"><a-modalv-model:visible="visible"@ok="handleOk"@cancel="handleCancel"width="1500px"><template#title>......
  • 算法-丑数2-构造小根堆
    intNthUglyNumber(intn){if(n==1)return1;List<long>arr=newList<long>();//这里用list,它会自己扩容,用数组就需要自己操作这些了arr.Add(1);int[]uglyArr={2,3,5};HashSet<long>hs=newHashSet<long>();hs.Add(1);......
  • 百强药企「普正药业」联合Smartbi构造以指标管理为核心的ABI平台
    江西普正制药股份有限公司(以下简称“普正药业”),是以天然植物药的成方制剂研发、生产、营销为主,集天然植物药种植、物流及国药文化传播、健康产业投资为一体的民营企业集集团,是中国中药百强企业,其天然植物药主导产品驰誉全国。普正药业致力于天然植物精品药,为医患提供慢性病与疑难病......
  • 观察基类与派生类的构造函数与析构函数的调用顺序
    一、设计思路1.定义一个哺乳动物类Mammal,2.派生出一个狗类Dog,3.定义一个dog类的对象,通过代码的执行顺序来判断观察观察基类与派生类的构造函数与析构函数的调用顺序。二、程序流程图。   三、代码实现。#pragmaonceclassMammal{public: Mammal(); ~Mammal();}......
  • 构造函数与默认构造函数
    钟表类#include<iostream>usingnamespacestd;classclock{public:clock(inth,intm,ints);clock();voidsettime(inth,intm,ints);voidshowtime();private: inthour,minute,second;};clock::clock(inth,intm,ints):hour(h),minute(m),second(s){}clock::cloc......
  • UVa 11129 An antiarithmetic permutation (构造题&想法题&分治)
    11129-AnantiarithmeticpermutationTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=2070Apermutationof n+1 isabijectivefunctionoftheinitial n+1......
  • 以阿里巴巴推荐的使用 ThreadPoolExecutor 构造函数自定义参数的方式来创建线程池
    importjava.util.concurrent.ArrayBlockingQueue;importjava.util.concurrent.ThreadPoolExecutor;importjava.util.concurrent.TimeUnit;publicclassThreadPoolExecutorDemo{privatestaticfinalintCORE_POOL_SIZE=5;privatestaticfinalintMAX......
  • Java-Day-8(方法重载 + 可变参数 + 作用域 + 构造方法 + this 关键字 )
    Java-Day-8方法重载(Overload)java中允许同一个类中,多个同名方法的存在,但要求形参列表不一致在调用方法时,通过所给的参数来选择执行的是哪个方法重载好处减轻了起名的麻烦减轻了记名的麻烦注意细节方法名必须相同参数列表必须不同形参类型或个数或顺序,......
  • Magic Line (牛客多校) (贪心,构造)
    题目大意:在平面直角坐标系中有偶数个点,求两个点使这两个点的连线两边点的数量相同且不经过任何一个点点的坐标都为整数,且绝对值不大于1000思路:我们先对点按横坐标排序,找到中间的两个点,如果这两个点横坐标不同,可以在两点之间找一条平行于y轴的直线如果相同的,因为点的纵坐标不......