第三章 图论 No.10无向图的双连通分量

文章目录

    • 定义
    • Tarjan求e-DCC
    • Tarjan求v-DCC
      • 395. 冗余路径
      • 1183. 电力
      • 396. 矿场搭建

定义

无向图有两种双连通分量

  1. 边双连通分量，e-DCC
  2. 点双连通分量，v-DCC

桥：删除这条无向边后，图变得不连通，这条边被称为桥
边双连通分量：极大的不含有桥的连通区域，说明无论删除e-DCC中的哪条边，e-DCC依旧连通 （该连通分量的任意边属于原图中的某条环）。此外，任意两点之间一定包含两条不相交（无公共边）的路径

割点：删除该点（与该点相关的边）后，图变得不连通，这个点被称为割点
点双连通分量：极大的不含有割点的连通区域

一些性质：

  1. 每个割点至少属于两个连通分量
  2. 任何两个割点之间的边不一定是桥，任何桥两边的端点不一定是割点，两者没有必然联系，一个点连通分量也不一定是边连通分量

image.png

image.png

Tarjan求e-DCC

无向图不存在横叉边
和有向图的强连通分量类似，引入dfn和low两个数组
如何找到桥？判断x->y的y是否能走到x之前（祖先节点），如果能走到，x和y在一个环中，删除这条边，其他点依然是连通的
所以x->y为桥：dfn[x] < low[y]

如何找到所有边的双连通分量？

  1. 删除所有桥
  2. 或者用stk辅助，若dfn[x] == low[x]，说明x出发一定走不到x的祖先节点，那么x和其父节点之间的边是桥，此时还在stk中的点为e-DCC的节点

这里使用第二种方式，模板：

void tarjan(int x, int from)
{
    dfn[x] = low[x] = ++ tp;
    stk[ ++ tt] = x;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
        }
        else if (i != (from ^ 1))
            low[x] = min(low[x], dfn[y]);
        if (dfn[x] < low[y])
                st[i] = st[i ^ 1] = true;
    }
    if (dfn[x] == low[x])
    {
        int y;
        cnt ++ ;
        do {
            y = stk[tt -- ];
            id[y] = cnt;
        } while (x != y);
    }
}

由于无向图要存储两条有向边，并且从数组的0下标开始存储，所以0，1、2，3…这样一对的边是互相反向的边，即i和i ^ 1为反向边
为什么与有向图的强连通分量不同，边双连通分量不需要使用st数组以标记栈中的元素？
因为无向图不存在横叉边的概念，就不会出现：x->y而y的dfn小于x，因为在无向图中y一定会向x遍历

Tarjan求v-DCC

如何求割点？low[y] >= dfn[x]，删除x节点后，y就是一颗独立的子树

  1. 如果x不是根节点，那么x是一个割点
  2. 如果x是根节点，至少有两个y满足以上关系

求割点的板子：

void tarjan(int x)
{
    dfn[x] = low[x] = ++ tp;
    int t = 0;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) t ++ ;
        }
        else low[x] = min(low[x], dfn[y]);
    }
    
    if (x != root) t ++ ;
    ans = max(ans, t);
}

将每个v-DCC向其包含的割点连一条边
缩点后，边的数量不会增加，点的数量可能会增加到两倍
image.png

tarjan求v-DCC与割点的板子：
一个孤立的点也是一个v-DCC，这里需要特判
若满足条件：low[y] >= dfn[x]，那么y的子树与x一起就是一个v-DCC
对于该节点是否是割点还需要特判，若该节点为根，并且与该节点相连的连通块数量为1，那么该节点就不是一个割点

void tarjan(int x)
{
	dfn[x] = low[x] = ++ tp;
	stk[ ++ tt ] = x;

	if (x == root && h[x] == -1)
	{
		++ dcnt;
		dcc[dcnt].push_back(x);
		return;
	}
	int t = 0; // 与x相连的连通块数量
	for (int i = h[x]; i != -1; i = ne[i])
	{
		int y = e[i];
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
			if (low[y] >= dfn[x])
			{
				dcnt ++, t ++ ;
				if (x != root || t > 1) st[x] = true; // x为割点
				int u;
				do {
					u = stk[tt -- ];
					dcc[dcnt].push_back(u);
				} while (u != y);
				dcc[dcnt].push_back(x);
			}
		}
		else low[x] = min(low[x], dfn[y]);
	}
}

395. 冗余路径

395. 冗余路径 - AcWing题库
image.png

任意两点间都存在两条没有重复边的路径，等价于整个图是一个双连通分量

将无向连通图的边双连通分量缩点后，得到的结构是一颗树，因为边双连通分量是不包含桥的结构，缩点后，图中只含有桥，即删除任意一条边后，图成为两个连通块，这是一个树结构

为了满足题意，需要向这颗树中添加边，使之成为边连通分量，那么要加几条边？
image.png

连接所有叶子节点，使这颗树结构成为双连通分量，至少需要加 [ ( c n t + 1 ) / 2 ] [(cnt + 1) / 2] [(cnt+1)/2]然后再下取整的边数，也就是将每个叶子节点相连，使环满足双连通分量的性质

注意cnt为1时需要特判

#include <iostream>
#include <cstring>
using namespace std;

const int N = 5010, M = 10010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int stk[N], tt, id[N];
bool st[N]; int d[N];
int n, m;

void add(int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}

void tarjan(int x, int from)
{
    dfn[x] = low[x] = ++ tp;
    stk[ ++ tt] = x;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
            if (dfn[x] < low[y])
                st[i] = st[i ^ 1] = true;
        }
        else if (i != (from ^ 1))
            low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        int y;
        cnt ++ ;
        do {
            y = stk[tt -- ];
            id[y] = cnt;
        } while (x != y);
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    int x, y;
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    
    tarjan(1, -1);
    for (int i = 0; i < idx; i ++ )
        if (st[i])
            d[id[e[i]]] ++ ;
    
    int res = 0;
    for (int i = 1; i <= cnt; ++ i )
        if (d[i] == 1) res ++ ;
        
    if (cnt == 1) puts("0");
    else printf("%d\n", (res + 1) / 2);
    return 0;
}

debug：^的优先级小于!=

可以不使用st数组标记桥：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 5010, M = 10010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int stk[N], tt, id[N];
int d[N];
int n, m;

void add(int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}

void tarjan(int x, int from)
{
    dfn[x] = low[x] = ++ tp;
    stk[ ++ tt] = x;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
        }
        else if (i != (from ^ 1))
            low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        int y;
        cnt ++ ;
        do {
            y = stk[tt -- ];
            id[y] = cnt;
        } while (x != y);
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    int x, y;
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    
    tarjan(1, -1);
    
    
    for (int x = 1; x <= n; ++ x )
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            int a = id[x], b = id[y];
            if (a != b) d[a] ++ ;
        }
        
    int res = 0;
    for (int i = 1; i <= cnt; i ++ )
        if (d[i] == 1) res ++ ;
    
    if (cnt == 1) puts("0");
    else printf("%d\n", (res + 1) / 2);
    return 0;
}

1183. 电力

1183. 电力 - AcWing题库
image.png

枚举所有割点，判断删除哪个割点后剩余的连通块数量最大
剩余的连通块数量为ans + cnt - 1
由于题目给定的图并不是一个连通图，所以可能存在多个连通块，cnt为连通块数量
枚举所有割点只能在一个连通块中枚举，此时其他连通块的数量为cnt - 1
又因为ans为删除割点后，剩余连通块最多的值，所以答案为ans + cnt - 1

这题的点编号从0开始

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10010, M = 30010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int ans, n, m, root;

void add(int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}

void tarjan(int x)
{
    dfn[x] = low[x] = ++ tp;
    int t = 0;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) t ++ ;
        }
        else low[x] = min(low[x], dfn[y]);
    }
    
    if (x != root) t ++ ;
    ans = max(ans, t);
}

int main()
{
    while (scanf("%d%d", &n, &m), n | m)
    {
        memset(h, -1, sizeof(h));
        memset(dfn, 0, sizeof(dfn));
        idx = tp = cnt = ans = 0;
        int x, y;
        for (int i = 0; i < m; ++ i )
        {
            scanf("%d%d", &x, &y);
            add(x, y), add(y, x);
        }
        for (root = 0; root < n; ++ root)
        {
            if (!dfn[root]) 
            {
                cnt ++ ;
                tarjan(root);
            }
        }
        printf("%d\n", ans + cnt - 1);
    }
    return 0;
}

debug：dfn数组没有置空

396. 矿场搭建

396. 矿场搭建 - AcWing题库
image.png

image.png
对于图中的每个连通块，分情况讨论：

  1. 若连通块无割点，那么任意设置两个救援点即可
  2. 若连通块中有割点，缩点：将每个割点依然看成一个点，将每个v-DCC向其包含的割点连线
  • 缩点后得到一棵树，对于叶子节点，需要建立救援点。因为只有一个点与其相连，若该点坍塌，需要在内部建立救援点。假设内部节点数量为cnt，方案数为cnt-1个，去除割点
  • 对于非叶子节点，无需建立救援点，因为无论与之相连的哪个割点坍塌，该节点都能走到叶子节点，而叶子节点已经建立救援点
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

typedef unsigned long long ULL;
const int N = 1010, M = 1010;
int h[N], e[M], ne[M], idx;
vector<int> dcc[N];
int dcnt, root;
int dfn[N], low[N], tp;
int stk[N], tt;
bool st[N];
int n, m;

void add(int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}

void tarjan(int x)
{
    low[x] = dfn[x] = ++ tp;
    stk[ ++ tt ] = x;
    if (x == root && h[x] == -1)
    {
        dcnt ++ ;
        dcc[dcnt].push_back(x);
        return;
    }
    int t = 0;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x])
            {
                t ++, dcnt ++ ;
                if (x != root || t > 1) st[x] = true;
                int u;
                do {
                    u = stk[tt -- ];
                    dcc[dcnt].push_back(u);
                } while (u != y);
                dcc[dcnt].push_back(x);
            }
        }
        else low[x] = min(low[x], dfn[y]);
    }
}

int main()
{
    int T = 1;
    while (scanf("%d", &m), m)
    {
        for (int i = 0; i < N; ++ i ) dcc[i].clear();
        memset(h, -1, sizeof(h));
        memset(dfn, 0, sizeof(dfn));
        memset(st, false, sizeof(st));
        tp = dcnt = idx = tt = n = 0;
        for (int i = 0; i < m; ++ i )
        {
            int x, y;
            scanf("%d%d", &x, &y);
            add(x, y), add(y, x);
            n = max(n, x), n = max(n, y);
        }
        for (root = 1; root <= n; ++ root )
            if (!dfn[root]) tarjan(root);
        
        ULL sum = 1; int ans = 0;
        for (int i = 1; i <= dcnt; ++ i )
        {
            int t = 0;
            for (int j = 0; j < dcc[i].size(); ++ j )
                if (st[dcc[i][j]]) 
                    t ++ ;
            if (t == 0) 
            {
                if (dcc[i].size() > 1) ans += 2, sum *= ((ULL)dcc[i].size() * (dcc[i].size() - 1)) / 2;
                else ans ++ ;
            }
            else if (t == 1) ans += 1, sum *= (dcc[i].size() - 1);
        }
        printf("Case %d: %d %llu\n", T ++ , ans, sum);
    }
    return 0;
}

debug：由于多组测试数据，没有初始化干净所有元素
最后统计救援点数量以及方案总数时，没有对孤立点进行特判

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/70910.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Jenkins 修改默认管理员帐号

Jenkins 修改默认管理员帐号

1、新增一个新的超级管理员用户&#xff0c;并验证能正常登录 2、进入 Jenkins 用户管理目录&#xff1a; /data/software/jenkins/users 3、修改超级管理文件夹的名称为其他名称&#xff0c;如&#xff1a;mv admin_*** ifadm_*** 4、重启Jenkins容器
阅读更多...
「C/C++」C/C++搭建程序框架

「C/C++」C/C++搭建程序框架

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「C/C」C/C程序设计&#x1f4da;全部专栏「UG/NX」NX二次开发「UG/NX」BlockUI集合「VS」Visual Studio「QT」QT5程序设计「C/C」C/C程序设计「Win」Windows程序设计「DSA」数据结构与算法「File」数据文件格式 目录 术语介绍…
阅读更多...
记录一下Java实体转json字段顺序问题

记录一下Java实体转json字段顺序问题

特殊需求&#xff0c;和C交互他们那边要求字段顺序要和他们定义的一致(批框架) 如下&#xff1a; Data public class UserDto {private String name;private Integer age;private String addr; }未转换前打印&#xff1a; 转换后打印&#xff1a; 可以看到转换为json顺序打印…
阅读更多...
029 - integer types 整数类型

029 - integer types 整数类型

MySQL支持SQL标准整数类型 INTEGER&#xff08;或INT&#xff09;和 SMALLINT。作为一个可扩展标准&#xff0c;MySQL也支持整数类型 TINYINT&#xff0c;MEDIUMINT和 BIGINT。下表显示了每种整数类型所需的存储空间和范围。 表11.1 MySQL支持的整数类型的必需存储和范围 类型…
阅读更多...
PLY模型格式详解【3D】

PLY模型格式详解【3D】

本文介绍PLY 多边形文件格式&#xff0c;这是一种用于存储被描述为多边形集合的图形对象。 PLY文件格式的目标是提供一种简单且易于实现但通用的格式足以适用于各种模型。 PLY有两种子格式&#xff1a;易于入门的 ASCII 表示形式和用于紧凑存储和快速保存和加载的二进制格式。 …
阅读更多...
案例14 Spring MVC文件上传案例

案例14 Spring MVC文件上传案例

基于Spring MVC实现文件上传&#xff1a; 使用commons-fileupload实现上传文件到本地目录。 实现上传文件到阿里云OSS和从阿里云OSS下载文件到本地。 1. 创建项目 选择Maven快速构建web项目&#xff0c;项目名称为case14-springmvc03。 ​ 2. 配置Maven依赖 <?xml ver…
阅读更多...
点淘的MCN机构申请详细入驻指南！

点淘的MCN机构申请详细入驻指南！

消费趋势的变化&#xff0c;来自消费人群的变化。 后疫情时代&#xff0c;经济复苏的反弹力度不足&#xff0c;人们开始怀疑我们正从前几年的消费升级&#xff0c;跌入消费降级的时代&#xff0c;但这并不能准确概括消费市场的变化。 仔细翻看各大奢侈品集团的财报&#xff0…
阅读更多...
nvm下载node导致npm报错无法使用

nvm下载node导致npm报错无法使用

有个依赖库需要更新下node&#xff0c;用nvm下载后项目跑不起来了&#xff0c;npm -v 还报错 其实一开始是npm下载不来&#xff0c;然后换了淘宝镜像后还是报错 然后就只能手动下载下了 进入node.js官网 https://nodejs.org/en/download 下载后注意要安装在你nvm目录中&#x…
阅读更多...
绕过 open_basedir

绕过 open_basedir

目录 0x01 首先了解什么是 open_basedir 0x02 通过命令执行绕过 0x03 通过symlink 绕过 &#xff08;软连接&#xff09; 0x04利用glob://绕过 方式1——DirectoryIteratorglob:// 方式2——opendir()readdir()glob:// 0x05 通过 ini_set和chdir来绕过 在ctfshow 72遇到…
阅读更多...
实践|Linux 中查找和删除重复文件

实践|Linux 中查找和删除重复文件

动动发财的小手&#xff0c;点个赞吧&#xff01; 如果您习惯使用下载管理器从互联网上下载各种内容&#xff0c;那么组织您的主目录甚至系统可能会特别困难。 通常&#xff0c;您可能会发现您下载了相同的 mp3、pdf 和 epub&#xff08;以及各种其他文件扩展名&#xff09;并将…
阅读更多...
OpenCV实例（九）基于深度学习的运动目标检测（一）YOLO运动目标检测算法

OpenCV实例（九）基于深度学习的运动目标检测（一）YOLO运动目标检测算法

基于深度学习的运动目标检测&#xff08;一&#xff09; 1.YOLO算法检测流程2.YOLO算法网络架构3.网络训练模型3.1 训练策略3.2 代价函数的设定 2012年&#xff0c;随着深度学习技术的不断突破&#xff0c;开始兴起基于深度学习的目标检测算法的研究浪潮。 2014年&#xff0c;…
阅读更多...
【Leetcode】155. 最小栈、JZ31 栈的压入、弹出序列

【Leetcode】155. 最小栈、JZ31 栈的压入、弹出序列

作者&#xff1a;小卢 专栏&#xff1a;《Leetcode》 喜欢的话&#xff1a;世间因为少年的挺身而出&#xff0c;而更加瑰丽。 ——《人民日报》 155. 最小栈 155. 最小栈 题目描述; 设计一个支持 push &#xff0c;pop &#xff0c;top …
阅读更多...
【Java学习】System.Console使用

【Java学习】System.Console使用

背景 在自学《Java核心技术卷1》的过程中看到了对System.Console的介绍&#xff0c;编写下列测试代码&#xff0c; public class ConsoleTest {public static void main(String[] args) {Console cs System.console();String name cs.readLine("AccountInfo: ");…
阅读更多...
【正点原子STM32连载】 第二章 APM32简介摘自【正点原子】APM32F407最小系统板使用指南

【正点原子STM32连载】 第二章 APM32简介摘自【正点原子】APM32F407最小系统板使用指南

1&#xff09;实验平台&#xff1a;正点原子stm32f103战舰开发板V4 2&#xff09;平台购买地址&#xff1a;https://detail.tmall.com/item.htm?id609294757420 3&#xff09;全套实验源码手册视频下载地址&#xff1a; http://www.openedv.com/thread-340252-1-1.html# 第二…
阅读更多...
excel将主信息和明细信息整理为多对多(每隔几行空白如何填充)

excel将主信息和明细信息整理为多对多(每隔几行空白如何填充)

excel导出的数据是主信息和明细信息形式。 方法如下:1、首先&#xff0c;从第一个单元格开始选中要填充的数据区域。2、按CtrlG或者F5调出定位对话框&#xff0c;点击左下角的【定位条件】。3、在【定位条件】中选择【空值】&#xff0c;然后点击【确定】按钮。4、按照上述操作…
阅读更多...
Vue输入框或者选择框无效，或者有延迟

Vue输入框或者选择框无效，或者有延迟

问题剖析 使用Vue这种成熟好用的框架&#xff0c;一般出现奇奇怪怪的问题都是因为操作不当导致的&#xff0c;例如没有合理调用组件、组件位置不正确、没有合理定义组件或者变量、样式使用不当等等... 解决方案 如果你也出现了输入框输入东西&#xff0c;但是没有效果…
阅读更多...
【idea】点击idea启动没反应

【idea】点击idea启动没反应

RT 点击idea启动的时候没反应&#xff0c;接着百度报错&#xff0c;基本跟他们的也不一样。 首先我是做版本升级。其次&#xff0c;我之前是破解的。如果你也是跟我一样的话&#xff0c;那问题可能就处在破解上了 解决方式 首先&#xff0c;是跟大部分解决思路一样。先找到项…
阅读更多...
项目部署（前后端分离）

项目部署（前后端分离）

1、前端项目 &#xff08;打包成dist文件,放到nginx的html目录下面&#xff09;&#xff0c;然后配置nginx 2、后端项目部署 使用之前的shell脚本&#xff08;然后赋予用户权限&#xff09;&#xff0c;最后运行脚本 查看进程
阅读更多...
网络安全 Day28-运维安全项目-加密隧道

网络安全 Day28-运维安全项目-加密隧道

运维安全项目-加密隧道 1. 加密隧道服务概述2. openVPN应用场景3. 虚拟机环境准备3.0 准备知识3.1 添加网卡![请添加图片描述](https://img-blog.csdnimg.cn/f155ca2804d84118b89a69da3688911e.png)3.2 配置内网&#xff08;LAN区段)3.3 虚拟机选择LAN区段3.4 书写eth1网卡配置…
阅读更多...
Mysql 和Oracle的区别

Mysql 和Oracle的区别

、mysql与oracle都是关系型数据库&#xff0c;Oracle是大型数据库&#xff0c;而MySQL是中小型数据库。但是MySQL是开源的&#xff0c;但是Oracle是收费的&#xff0c;而且比较贵。 1 2 mysql默认端口&#xff1a;3306&#xff0c;默认用户&#xff1a;root oracle默认端口&…
阅读更多...
最新文章

Copyright @ 2022~2023