【算法每日一练]-图论（保姆级教程篇12 tarjan篇）#POJ3352道路建设 #POJ2553图的底部 #POJ1236校园网络 #缩点

2023-12-03 20:01
文章标签 算法 建设 教程 每日 图论 网络 保姆 底部 tarjan 道路 校园 缩点 poj3352 poj1236 poj2553

本文主要是介绍【算法每日一练]-图论（保姆级教程篇12 tarjan篇）#POJ3352道路建设 #POJ2553图的底部 #POJ1236校园网络 #缩点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

        

POJ3352：道路建设

        思路：

POJ2553：图的底部

       思路：

POJ1236校园网络

       思路：

缩点： 

      思路：

        

        

POJ3352：道路建设

        
由于道路要维修，维修时候来回都不能走，现要在各个景点间建设新道路以便维修时候也能保证任何两个景点之间可以相互到达，求最少的新道路数量
任何一对景点间最多只能在它们之间有一条道路(没有重边)。道路一开始是联通的

输入：
3 3
1 2
2 3
1 3
或
10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10

        
思路：

先求解边双连通分量，然后缩点，然后通过加边再把新图变成双连通图。

加边原理是这样的：
先统计叶节点个数为k，(k+1)/2就是要建的边数。因为在树中，给叶节点加边一定会产生环

说一下tarjan后的操作 

for(int u=1;u<=n;u++)for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(low[u]!=low[v]) deg[low[u]]++;//遍历新图的边（其实就是旧图的桥）
//有重边也要记录。low[u]就是连通分量号，每个连通分量中只有桥的点才有度}int leaf=0;
//		for(int i=1;i<=n;i++){
//			cout<<i<<' '<<deg[i]<<' '<<low[i]<<'\n';//看详情
//		}for(int i=1;i<=n;i++){//检查每个连通分量号的度（一定不为零）if(deg[i]==1) leaf++;//度是1就是叶子}cout<<(leaf+1)/2<<'\n';

 首先是缩点：low是连通分量号，把度(无向图没有入度出度之分)统计到桥点身上（很像并查集中的缩点到祖宗点身上），注意我们这种缩点的过程肯定会遇到重边。此题中的重边是不能去掉的，否则叶节点会统计错误！！！

然后统计度为1就是叶子就行。

        

对于重边：有时候必须要，有时候不影响，有时候也必须去重。要仔细分析！

#include <bits/stdc++.h>//无向图的桥
using namespace std;
const int maxn=1000+5;
int n,m;
int head[maxn],cnt;
struct node{int to,next;}e[maxn*2];
int low[maxn],dfn[maxn],deg[maxn],num;//deg是度(无向图没有入度和出度之分)void add(int u,int v){ e[++cnt]=(node){v,head[u]};head[u]=cnt;}void tarjan(int u,int fa){dfn[u]=low[u]=++num;//初始化for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==fa) continue;//不可以走父子边回去if(!dfn[v]){//没访问过就递归访问tarjan(v,u);low[u]=min(low[u],low[v]);//low是自己或子孙能走回的最小dfn}else{//可以从非父子边回去就要获取dfn值，就是该点能回到的最小dfnlow[u]=min(low[u],dfn[v]);}}
}void init(){memset(head,0,sizeof(head));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(deg,0,sizeof(deg));cnt=num=0;
}int main(){while(cin>>n>>m){init();int u,v;while(m--){cin>>u>>v;add(u,v);add(v,u);}tarjan(1,0);//求边双连通分量for(int u=1;u<=n;u++)for(int i=head[u];i;i=e[i].next){int v=e[i].to;//遍历新图的边（其实就是旧图的桥）if(low[u]!=low[v]) deg[low[u]]++;
//有重边也要记录。low[u]就是连通分量号，每个连通分量中只有桥的点才有度}int leaf=0;
//		for(int i=1;i<=n;i++){
//			cout<<i<<' '<<deg[i]<<' '<<low[i]<<'\n';//看详情
//		}for(int i=1;i<=n;i++){//检查每个连通分量号的度（一定不为零）if(deg[i]==1) leaf++;//度是1就是叶子}cout<<(leaf+1)/2<<'\n';}	
}

        

        

POJ2553：图的底部

        
有向图中若v可以到的任何一个u，u也可以到v，则v是一个sink点，图的底部是由所有sink点构成的，按顺序输出所有sink点编号，没有sink就输出一个空行

输::
3 3
1 3 2 3 3 1
2 1
1 2
0

思路：

你只需要输出出度为0的连通分量中的所有点编号即可
                

for(int u=1;u<=n;u++)for(int i=head[u];i;i=e[i].next){//对所有边进行判断是不是连接着两个分量int v=e[i].to;if(be[u]!=be[v]){//有重边out[be[u]]++;//缩点}}
int f=1;
for(int i=1;i<=n;i++){if(!out[be[i]]){//输出出度为0的连通分量中的点if(f) f=0;else cout<<" ";//一个数前面有个空格cout<<i; }
}

不同于无向图，有向图的连通分量号我们用一个be数组存起来 

然后对所有边进行判断是不是连接着两个分量，然后对新树中的边统计出度，输出出度为0的连通分量中的点

#include <bits/stdc++.h>
using namespace std;
const int maxn=5050;
bool ins[maxn];//标记是否在栈中
int n,m;
int head[maxn],be[maxn],out[maxn];//be是属于哪个连通分量，out是缩点的出度
int low[maxn],dfn[maxn],num,id,cnt;
stack <int> s;
struct node{int to,next;}e[maxn*2];void add(int u,int v){ e[++cnt]=(node){v,head[u]};head[u]=cnt;}void tarjan(int u){dfn[u]=low[u]=++num;//dfn访问序号，low是能走回到的最早的dfnins[u]=1;s.push(u);//第一次访问节点时候入栈for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(!dfn[v]){//没访问过就递归访问tarjan(v);low[u]=min(low[u],low[v]);//获取孩子的最小的low值   }else if(ins[v]){//已经访问过且在栈中获取dfn号low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){//low[u]==dfn[u]时，则从栈中不断弹出节点，直到x出栈停止。弹出的节点就是同一个连通分量的int v;do{//一定要先执行再判断v=s.top();s.pop();be[v]=id;//把这些弹出的点标记同一个id号(连通分量号)ins[v]=0;}while(v!=u);//直到是自己为止id++;}
}void init(){memset(head,0,sizeof(head));memset(low,0,sizeof(low));memset(ins,0,sizeof(ins));memset(dfn,0,sizeof(dfn));memset(out,0,sizeof(out));memset(be,0,sizeof(be));cnt=num=0;id=1;
}int main(){while((cin>>n)&&n){//点数cin>>m;//边数init();int u,v;while(m--){cin>>u>>v;add(u,v);}for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);//有向图}for(int u=1;u<=n;u++)for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(be[u]!=be[v]){//有重边out[be[u]]++;//缩点}}int f=1;for(int i=1;i<=n;i++){if(!out[be[i]]){//输出出度为0的连通分量中的点if(f) f=0;else cout<<" ";//（输出格式罢了，不用在乎这里）cout<<i; }}}	
}

        

        

POJ1236校园网络

        
每所学校都有一份发学校名单。计算至少先发给多少个学校才能使软件传到所有学校(任务1)，计算至少增加多少扩展才能将软件发给任意学校结果都能传到所有学校(扩展就是将新成员引入一所学校的接收者名单)
5
2 4 3 0
4 5 0
0
0
1 0

        

思路：

        
任务1：每一个入度为0的连通分量都必须收到一个软件，计算个数。
任务2：每个连通分量必须既有入度也有出度，即入度为0的连通分量必须扩展一下，出度为0的连通分量必须也扩展一下（入度和出度对接，输出max就行）

#include <bits/stdc++.h>//有向图的强连通分量
using namespace std;
const int maxn=5050;
bool ins[maxn];
int n,m,cnt;
int head[maxn],be[maxn],in[maxn],out[maxn];//be是属于哪个连通分量  in,out是每个连通分量的入度和出度
int low[maxn],dfn[maxn],num,id;
stack <int> s;
struct node{int to,next;}e[maxn*2];void add(int u,int v){ e[++cnt]=(node){v,head[u]};head[u]=cnt;}void tarjan(int u){dfn[u]=low[u]=++num;//dfn访问序号，low是能走回到的最早的dfnins[u]=1;s.push(u);//第一次访问节点时候入栈for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(!dfn[v]){//没访问过就递归访问tarjan(v);low[u]=min(low[u],low[v]);//获取孩子的最小的low值   }else if(ins[v]){//已经访问过且在栈中获取dfn号low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){//low[u]==dfn[u]时，则从栈中不断弹出节点，直到x出栈停止。弹出的节点就是同一个连通分量的int v;id++;do{//一定要先执行再判断v=s.top();s.pop();be[v]=id;//把这些弹出的点标记同一个id号(连通分量号)ins[v]=0;}while(v!=u);//直到是自己为止}
}int main(){cin>>n;int v;//n为学校数量for(int i=1;i<=n;i++){while(cin>>v&&v)add(i,v);//表示接收i的v学校，以0结尾}for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);}for(int u=1;u<=n;u++)for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(be[u]!=be[v]){//有重边，可以输出一下in[be[v]]++;out[be[u]]++;//统计入度和出度，来缩点}}if(id==1){//一共只要一个连通分量的话要特判cout<<1<<'\n';cout<<0<<'\n';return 0;}int ans1=0,ans2=0;//for(int i=1;i<=n;i++)cout<<i<<' '<<be[i]<<'\n';for(int i=1;i<=id;i++){//	cout<<i<<" in"<<' '<<in[i]<<" , "<<"out"<<' '<<out[i]<<'\n';if(!in[i]) ans1++;if(!out[i]) ans2++;}cout<<ans1<<'\n';cout<<max(ans1,ans2)<<'\n';	
}

        

        

        

缩点： 

        

         

思路：

有向图中的强连通分量中的所有权值一定要全部加上，所以缩点建出新的DAG图，然后转化成了每个点走一次求最大点权值和
设置dp[v]表示到v点的最大权值和。 dp[v]=max(dp[u])即可，也就是要先求dp[u]再求dp[v]，topo排序求一边就行了。完了！
        

	if(low[u]==dfn[u]){//low[u]==dfn[u]时，则从栈中不断弹出节点，直到x出栈停止。弹出的节点就是同一个连通分量的int v;	do{//一定要先执行再判断v=s.top();s.pop();be[v]=u;//把这些弹出的点标记同一个id号(连通分量号)ins[v]=0;if(u==v)break;//自己不要和自己加p[u]+=p[v];}while(v!=u);//直到是自己为止}

首先是缩点操作，要把该连通分量中点的权值加给连通分量点自己(类似无向图的桥点)， 

        

for (int i=1;i<=m;i++)//遍历每个边{int u=be[e[i].from],v=be[e[i].to];//from是起点，to是终点if (u!=v)//不同的分量号点间进行建边，有重边也不影响topo结果{newe[++tt]=(node){v,hh[u],u};hh[u]=tt;in[v]++;//建新边过程，相当于add功能}}

然后是给新DAG图建边，以便后面topo。

        

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+15;
int n,m,tot,head[maxn],tt,hh[maxn],p[maxn];//p是每个点的权值,head和tot和e是原图的，hh和tt和newe是新图的
int num,low[maxn],dfn[maxn],ins[maxn],be[maxn];//be是每个所属的连通分量号
int in[maxn],dp[maxn];
stack<int>s;
struct node{int to,next,from;}e[maxn*10],newe[maxn*10];void add(int u,int v){e[++tot]=(node){v,head[u],u};head[u]=tot;}void tarjan(int u){dfn[u]=low[u]=++num;//dfn访问序号，low使能回溯到的最早的dfnins[u]=1;s.push(u);//第一次访问节点时候入栈for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(!dfn[v]){//没访问过就递归访问tarjan(v);low[u]=min(low[u],low[v]);//获取孩子的最小的low值   }else if(ins[v]){//已经访问过且在栈中获取dfn号low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){//low[u]==dfn[u]时，则从栈中不断弹出节点，直到x出栈停止。弹出的节点就是同一个连通分量的int v;	do{//一定要先执行再判断v=s.top();s.pop();be[v]=u;//把这些弹出的点标记同一个id号(连通分量号)ins[v]=0;if(u==v)break;//自己不要和自己加p[u]+=p[v];}while(v!=u);//直到是自己为止}
}int topo()
{queue <int> q;int tot=0;for (int i=1;i<=n;i++){if(be[i]==i&&!in[i]){q.push(i);dp[i]=p[i];}}while (!q.empty()){int u=q.front();q.pop();for (int i=hh[u];i;i=newe[i].next){int v=newe[i].to;dp[v]=max(dp[v],dp[u]+p[v]);//要最大的起点嘛in[v]--;if (in[v]==0) q.push(v);}}int ans=0;for (int i=1;i<=n;i++)ans=max(ans,dp[i]);return ans;
}
int main()
{scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)scanf("%d",&p[i]);//权值for (int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);add(u,v);}for (int i=1;i<=n;i++)if (!dfn[i]) tarjan(i);for (int i=1;i<=m;i++){int u=be[e[i].from],v=be[e[i].to];//from是起点，to是终点if (u!=v)//不同的分量号点间进行建边，有重边也不影响topo结果{newe[++tt]=(node){v,hh[u],u};hh[u]=tt;in[v]++;//建新边过程，相当于add功能}}printf("%d",topo());
}

这篇关于【算法每日一练]-图论（保姆级教程篇12 tarjan篇）#POJ3352道路建设 #POJ2553图的底部 #POJ1236校园网络 #缩点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/450698。

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
Makefile简明使用教程

Makefile简明使用教程

文章目录 规则makefile文件的基本语法：加在命令前的特殊符号：.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具，常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
Centos7安装JDK1.8保姆版

Centos7安装JDK1.8保姆版

工欲善其事，必先利其器。这句话同样适用于学习Java编程。在开始Java的学习旅程之前，我们必须首先配置好适合的开发环境。 通过事先准备好这些工具和配置，我们可以避免在学习过程中遇到因环境问题导致的代码异常或错误。一个稳定、高效的开发环境能够让我们更加专注于代码的学习和编写，提升学习效率，减少不必要的困扰和挫折感。因此，在学习Java之初，投入一些时间和精力来配置好开发环境是非常值得的。这将为我
阅读更多...
Linux 网络编程 --- 应用层

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码： 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口，https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2