原先有一个图,dfs序是1,2,...,n, 但是其中一些边被破坏,给定被破坏边后的图,求最少要加几条边,可以使图的dfs序为1,2,...,n

这篇具有很好参考价值的文章主要介绍了原先有一个图,dfs序是1,2,...,n, 但是其中一些边被破坏,给定被破坏边后的图,求最少要加几条边,可以使图的dfs序为1,2,...,n。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目文章来源地址https://www.toymoban.com/news/detail-792835.html

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int maxn = 2e5 + 5, maxm = 2e3 + 5;
int a[maxn];
int nxt;//下一个应该遍历的结点
int res = 0;
int n, m;
vector<int> G[maxn];
void dfs(int u){
    if(u == nxt) nxt++;
    for(int i = 0; i < G[u].size();){//这里不写i++
        int v = G[u][i];
        if(v < nxt){//之前遍历过的结点,跳过
            i++;
            continue;
        } 
        if(v > nxt){
            res++;
            dfs(nxt);//这里不i++, 等把nxt~v-1的结点遍历完再dfs(v)
            /*
            1
            4 1
            1 3
            */
        }
        else{
            dfs(v);
            i++;
        }
    }
}
void solve(){
	cin >> n >> m;
    for(int i = 1; i <= n; i++){
        G[i].clear();
    }
    res = 0;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
//         if(u == v) continue;
//         if(u > v) swap(u, v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        sort(G[i].begin(), G[i].end());//按顺序来
    }
    nxt = 1;
    while(nxt <= n){
        res++;//向nxt连一条边
        dfs(nxt);
    }
    cout << res - 1 << '\n';//减去向1连的一条边
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while(T--){
		solve();
	}
}

到了这里,关于原先有一个图,dfs序是1,2,...,n, 但是其中一些边被破坏,给定被破坏边后的图,求最少要加几条边,可以使图的dfs序为1,2,...,n的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • unity在其中一个脚本,怎么引用另一个脚本的函数

    在 Unity 中,有多种方式可以引用另一个脚本的函数,其中比较常用的有以下几种: 通过获取组件引用: 如果两个脚本都是同一个游戏对象上的组件,您可以通过GetComponent() 方法获取目标脚本的实例,并直接调用其中的函数,例如: 通过查找对象: 如果您想要在一个游戏对

    2024年02月16日
    浏览(41)
  • 根据一个List生成另外一个List,修改其中一个,导致另外一个List也在变化

    1、两个List复制         SysDic aSysDic = new SysDic();         aSysDic.setDkey(\\\"1\\\");         aSysDic.setDnote(\\\"12\\\");         SysDic bSysDic = new SysDic();         bSysDic.setDkey(\\\"2\\\");         bSysDic.setDnote(\\\"23\\\");         SysDic cSysDic = new SysDic();         cSysDic.setDkey(\\\"3\\\");         cSysDic.setDnote(\\\"34\\\");  

    2024年02月10日
    浏览(38)
  • 有一个3行4列的矩阵,编程求出其中最大

    任务描述 相关知识 二维数组的定义 二维数组的引用 二维数组的初始化 编程要求 测试说明 任务描述 本关任务:有一个3行4列的矩阵,编程求出其中最大的那个元素的值,以及它所在的行号与列号。 相关知识 二维数组的定义 在实际问题中有很多变量是二维的或多维的,因此

    2024年02月07日
    浏览(54)
  • el-form实现其中一个填写即可的校验

       

    2024年02月13日
    浏览(45)
  • 【Elasticsearch】ES查询出满足以下其中任意一个条件的订单

    需求:最近测试经理给我这边提出一个需求,大致可以描述为查询出\\\" 购买的商品名称中包含’测试’ “、” 订单的收货地址包含’B360’ \\\"、“收货人手机号为测试人员的手机号”; 一、实现方案 当时评估了两种方案: ①、直接从数据库中查询; ②、从ES中查询; 方案①

    2024年02月16日
    浏览(40)
  • postman如何发送json请求其中file字段是一个图片

    在Postman中发送一个包含文件(如图片)的JSON请求通常意味着你需要发送一个multipart/form-data请求。因为在JSON中直接嵌入二进制文件数据(如图片)通常不是一个有效的做法。下面是如何在Postman中发送这样的请求的步骤: 打开Postman并创建一个新的请求 。 设置请求类型为 PO

    2024年04月28日
    浏览(32)
  • 保姆级的Arduino循迹小车研发日志及一些坑(其中包含L298N、Arduino、TCRT5000以及1:48的TT电机的使用)

    开发要求如下: 引言:为什么会用到 米思齐 这个青少年编程软件是有两个原因: 接到了某所小学的研发项目需求,研发成果给小学生参加无人车循迹比赛。 实验室的师弟师妹并不是所有都有编程基础,因此米思齐可以作为简单的编程引入课程。 首先我认为 TCRT5000红外循迹

    2023年04月08日
    浏览(45)
  • 有一个 3*4 的矩阵,找出其中值最大的元素,及其行列号

    首先学会输入二维数组;然后知道如何比较求最大值;最后就是格式问题; 3运行代码: 4总结: 感谢各位的阅读,以上就是“C语言怎么有一个 3*4 的矩阵,找出其中值最大的元素,及其行列号”的内容了,经过本文的学习后,相信大家对C语言这一问题有了更深刻的体会,具

    2024年02月04日
    浏览(49)
  • 【线性代数】两个向量组等价,其中一个向量组线性无关,另一个向量组也是线性无关吗?

    两个向量组等价,其中一个向量组线性无关,另一个向量组也是线性无关吗? 不一定,当两个向量组中的向量个数也相同时,结论才成立.若向量个数不相同,结论不成立. 例如: 向量组一:(1,0),(0,1) 向量组二:(1,0),(0,1),(1,1) 两个向量组等价,向量组一线性无关,向量组二线性相关 参考

    2024年02月02日
    浏览(52)
  • # java合并两个list 并去重,指定保留其中一个list的重复数据

    在Java中,有多种方法可以合并两个List并去重,指定保留其中一个List的重复数据。下面介绍几种常见的方法,并附上代码示例。 该方法首先将一个List的所有元素加入到目标List中,然后遍历另一个List,如果目标List中不包含该元素,则将该元素加入到目标List中。最后得到的就

    2024年02月02日
    浏览(71)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包