acwing-395. 冗余路径(Tarjan双连通分量)

acwing-395. 冗余路径(Tarjan双连通分量)为了从 F 个草场中的一个走到另一个,奶牛们有时不得不路过一些她们讨厌的可怕的树。奶牛们已经厌倦了被迫走某一条路,所以她们想建一些新路,使每一对草场之间都会至少有两条相互分离的路径,这样她们就有多一些选择。每对草场之间已经有至少一条路径。给出所有 R 条双向路的描述,每条路连接了两个不同的草场,请计算最少的新建道路的数量,路径由若干道路首尾相连而成。两条路径相互分离,是指两条路径没有一条重合的道路。但是,两条分离的路径上可以有一些相同的草场。对于同一对草场之间,可能已经有两条不同的道路,你也可以

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

为了从 F 个草场中的一个走到另一个,奶牛们有时不得不路过一些她们讨厌的可怕的树。

奶牛们已经厌倦了被迫走某一条路,所以她们想建一些新路,使每一对草场之间都会至少有两条相互分离的路径,这样她们就有多一些选择。

每对草场之间已经有至少一条路径。

给出所有 R 条双向路的描述,每条路连接了两个不同的草场,请计算最少的新建道路的数量,路径由若干道路首尾相连而成。

两条路径相互分离,是指两条路径没有一条重合的道路。

但是,两条分离的路径上可以有一些相同的草场。

对于同一对草场之间,可能已经有两条不同的道路,你也可以在它们之间再建一条道路,作为另一条不同的道路。

输入格式
第 1 行输入 F 和 R。

接下来 R 行,每行输入两个整数,表示两个草场,它们之间有一条道路。

输出格式
输出一个整数,表示最少的需要新建的道路数。

数据范围
1≤F≤5000,
F−1≤R≤10000

输入样例:
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
输出样例:
2
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
const int M = 2e4 + 10;
struct Edge{ 
   
    int v,next;
}edge[M];
int degree[N];
int scc[N],sccno;
int low[N],num[N],dfn;
int isbridge[M];
int head[N],cnt;
int sta[N],in_sta[N],top;
void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
void Tarjan(int u,int from){ 
   
    low[u] = num[u] = ++ dfn;
    sta[top ++] = u,in_sta[u] = true;
    for(int i = head[u];~i;i = edge[i].next){ 
   
        int v = edge[i].v;
        if(!num[v]){ 
   
            Tarjan(v,i);
            low[u] = min(low[u],low[v]);
            if(low[v] > num[u]){ 
   
                isbridge[i] = isbridge[i ^ 1] = true;
            }
        }
        else if(i != (from ^ 1)){ 
   
            low[u] = min(low[u],num[v]);
        }
    }
    if(low[u] == num[u]){ 
   
        sccno ++;
        while(1){ 
   
            int t = sta[-- top];
            scc[t] = sccno;
            in_sta[t] = false;
            if(t == u)break;
        }
    }
}
int main(){ 
   
    memset(head,-1,sizeof head);
    int n,m;
    cin >> n >> m;
    int x,y;
    for(int i = 0;i < m;i ++){ 
   
        cin>>x>>y;
        add(x,y),add(y,x);
    }
    Tarjan(1,-1);
    for(int i = 0;i < cnt ;i ++){ 
   
        if(isbridge[i]){ 
   
            degree[scc[edge[i].v]] ++;
        }
    }
    int c = 0;
    for(int i = 1;i <= sccno;i ++){ 
   
        if(degree[i] == 1)c ++;
    }
    cout<<(c + 1) / 2;
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168617.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • js数组转对象的方法_js json对象转换成数组

    js数组转对象的方法_js json对象转换成数组记录将数组转成对象方法letarray=[1,2,3,4,5];letobj={};obj=(Object.assign({},array)console.log(obj);//{1,2,3,4,5}

  • rsyslogd内存占用率高_怎么减少系统内存占用

    rsyslogd内存占用率高_怎么减少系统内存占用用top,用ps都能看到。相伴的systemd-journalcpu和内存占用也很高。systemd-journal使用了持久化模式。其中一个服务1秒钟内打非常多的日志。一天好几个G。另外,sudojournalctl–verify也有错误输出。其他没什么异常。https://blog.csdn.net/qq_25518029/article/details/12001067…

  • django和drf_类中的方法可以序列化么

    django和drf_类中的方法可以序列化么前言上一篇文章我们讲述了序列化,这篇就带大家一起来实现以下序列化Serializer我们使用序列化类Serializer,我们来看下源码结构,这里推荐使用pycharm左边导航栏的Structu

  • Linux小技巧:tail -f —— 查看动态文本

    Linux小技巧:tail -f —— 查看动态文本说道查看文本:大家很肯定有用过cat:一次查看所有内容,不过文本行数过多,不能全部显示[root@localhostyum.repos.d]#cat163.repo.bak[163repo]name=linuxredhat163.repobaseurl=http://mirrors.163.com/centos/7/os/x86_64/gpgcheck=0enabl…

  • 简单介绍T检验和卡方检验「建议收藏」

    简单介绍T检验和卡方检验「建议收藏」最近在看统计学方面的知识,正好有个学妹问我一些检验方面的东西,以前读书那会的统计学知识早已忘记,经过半天的努力,又把知识给拾起来了,下面简单介绍下T检验和卡方检验。1. T检验适用范围:主要用于样本含量较小(例如n总体标准差σ未知的正态分布。其中最常用的是单总体t检验,单总体t检验是检验一个样本平均数与一个已知的总体平均数的差异是否显著。当总体分布是正态分布,如总体标准差未知

  • 当前Activity跳转到另外一个Activity「建议收藏」

    当前Activity跳转到另外一个Activity「建议收藏」当前Activity跳转到另外一个ActivityStep1:创建firest_layout.xml文件.添加一个Button:&lt;Buttonandroid:id="@+id/button1"android:layout_width="wrap_content"android:layout_height="wrap_content"android…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号