【算法每日一练]-图论(保姆级教程篇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值,就是该点能回到的最小dfn
			low[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是能走回到的最早的dfn
	ins[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是能走回到的最早的dfn
	ins[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使能回溯到的最早的dfn
	ins[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());
}

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

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

相关文章

Python实战:批量加密Excel文件指南

更多Python学习内容&#xff1a;ipengtao.com 大家好&#xff0c;我是彭涛&#xff0c;今天为大家分享 Python实战&#xff1a;批量加密Excel文件指南&#xff0c;全文3800字&#xff0c;阅读大约10分钟。 在日常工作中&#xff0c;保护敏感数据是至关重要的。本文将引导你通过…

跟着Nature Communications学习Hisat-Trinity-PASA等分析流程

一边学习&#xff0c;一边总结&#xff0c;一边分享&#xff01; 详细教程请访问&#xff1a; 组学分析流程 本期分析流程 Hisat2-SamtoolsTrinity_GG_denovoPASA … 本期教程文章 题目&#xff1a;Genomic insights into local adaptation and future climate-induced vu…

untiy webgl常见问题与操作

文章目录 1 untiy和网页相互通信2 打开新页面&#xff08;同标签页和新标签页&#xff09;3 获取网页的URL4 解析Url内的参数5 后处理与色彩空间问题 1 untiy和网页相互通信 看这个文章 2 打开新页面&#xff08;同标签页和新标签页&#xff09; 先看本文untiy和网页相互通信…

代码随想录算法训练营 ---第五十三天

第一题&#xff1a; 简介&#xff1a; 本题和昨天的最大重复子串问题很相似&#xff0c;只不过本题不一定是连续的。 动规五部曲分析如下&#xff1a; 确定dp数组&#xff08;dp table&#xff09;以及下标的含义 dp[i][j]&#xff1a;长度为i-1 的字符串text1与长度为j-1的…

Git 分支详解

目录 1. Git 分支管理 2. 如何自己创建分支&#xff1f; 3. 创建分支修改内容&#xff0c;之后合并到主分支 4. 删除分支 5. 出现 merge 冲突如何解决 6. 分支策略 前言 之前只是知道有 master 分支这个东西&#xff0c;但是具体是啥意思还是不知道&#xff0c;今天详…

【面试HOT200】二叉树——广度优先搜索篇

系列综述&#xff1a; &#x1f49e;目的&#xff1a;本系列是个人整理为了秋招面试的&#xff0c;整理期间苛求每个知识点&#xff0c;平衡理解简易度与深入程度。 &#x1f970;来源&#xff1a;材料主要源于【CodeTopHot200】进行的&#xff0c;每个知识点的修正和深入主要参…

MFC 绘制单一颜色圆形、渐变颜色边框圆形、渐变填充圆形以及绘制三角函数正弦函数曲线.

MFC 绘制三种不同圆形以及绘制正弦函数曲线 本文使用visual Studio MFC 平台实现绘制单一颜色圆形、渐变颜色边框圆形、渐变填充圆形以及绘制三角函数正弦函数曲线. 关于基础工程的创建请参考 01-Visual Studio 使用MFC 单文档工程绘制单一颜色直线和绘制渐变颜色的直线 02-vis…

设计模式-结构型模式之适配器设计模式

文章目录 一、结构型设计模式二、适配器模式 一、结构型设计模式 这篇文章我们来讲解下结构型设计模式&#xff0c;结构型设计模式&#xff0c;主要处理类或对象的组合关系&#xff0c;为如何设计类以形成更大的结构提供指南。 结构型设计模式包括&#xff1a;适配器模式&…

【前沿技术】扩散模型是什么

0. 前言 扩散模型的灵感来自非平衡热力学。他们定义了一个马尔可夫扩散步骤链&#xff0c;以缓慢地将随机噪声添加到数据中&#xff0c;然后学习逆转扩散过程以从噪声中构建所需的数据样本。与VAE或流动模型不同&#xff0c;扩散模型是通过固定程序学习的&#xff0c;并且潜在变…

Linux下activemq的安装与安装成功确认

一、下载 apache-activemq-5.14.0-bin.tar.gz 二、安装 将压缩包拷入linux内&#xff0c;进行解压tar -zxvf apache-activemq-5.14.0-bin.tar.gz&#xff0c;与redis、nginx不同的是&#xff0c;active解压不需要安装就可以直接启动&#xff01; 启动命令&#xff1a;./bin…

PMP考试解析

PMP考试解析 考试动机 1、裁员太猛了&#xff0c;多一条生存技能 2、学习管理技能往管理方向靠 3、转行&#xff0c; 考试路径 1、报班费&#xff1a; 考PMP必须报班&#xff0c;不然没有考试资格&#xff08;无语的规定&#xff09; &#xff08;类似于考驾照&#xff0c;…

PhotoZoom 2024中文版全新版本震撼来袭!PhotoZoom 8怎么使用

PhotoZoom 2023&#xff08;PhotoZoom 8&#xff09;全新版本震撼来袭。 一款划时代的、技术上产生革命性影响的数码图片放大工具。 我们获取图片的方法&#xff0c;一般是从度娘图片和各个图库里找素材。但一般网上搜索到的很多图片像素都非常小&#xff0c;普通方法放大就像打…

DeDeCMS v5.7 SP2 正式版 前台任意用户密码修改(漏洞复现)

1.环境搭建 PHP 5.6 DeDeCMSV5.7SP2 正式版 安装phpstudy&#xff0c;https://www.xp.cn/小皮面板 先启动Apache2.4.39和MySQL5.7.26 如果他会让你下载&#xff0c;点击是就好&#xff01; 让后点击网站—>点击创建网站 域名自己创建&#xff0c;自己取 其他的不变 点击…

详解Spring对Mybatis等持久化框架的整合

&#x1f609;&#x1f609; 学习交流群&#xff1a; ✅✅1&#xff1a;这是孙哥suns给大家的福利&#xff01; ✨✨2&#xff1a;我们免费分享Netty、Dubbo、k8s、Mybatis、Spring...应用和源码级别的视频资料 &#x1f96d;&#x1f96d;3&#xff1a;QQ群&#xff1a;583783…

RPG项目01_脚本代码

基于“RPG项目01_场景及人物动画管理器”&#xff0c;我们创建一个XML文档 在资源文件夹下创建一个文件夹&#xff0c; 命名为Xml 将Xnl文档拖拽至文件夹中&#xff0c; 再在文件夹的Manager下新建脚本LoadManager 写代码&#xff1a; using System.Collections; using System…

【目标检测实验系列】YOLOv5创新点改进实验:通过转置卷积,动态学习参数,减少上采用过程特征丢失,提高模型对目标的检测精度!(超详细改进代码流程)

1. 文章主要内容 本篇博客主要涉及两个主体内容。第一个&#xff1a;简单介绍转置卷积的原理。第二个&#xff1a;基于YOLOv5 6.x版本&#xff0c;将Neck部分的upSample改为nn.ConvTranspose2d转置卷积&#xff08;通读本篇博客需要10分钟左右的时间&#xff09;。 小提…

QNX常用调试方法

QNX常用调试方法 1. top 查询系统状态最常用的工具是top&#xff0c;它可以显示系统资源的使用情况。我们最关心的通常是系统可用内存和CPU使用率。如果CPU使用率过高可能是因为某些应用存在bug&#xff0c;重点关注下面显示的占用CPU资源最多的几个线程。如果可用内存太少&am…

史上最全低代码平台盘点!三分钟盘点2023年顶尖二十个低代码平台!

史上最全低代码平台盘点&#xff01;三分钟盘点2023年顶尖二十个低代码平台&#xff01; 什么是低代码平台&#xff1f;2023年顶尖二十大低代码平台&#xff0c;哪个值得一试&#xff1f;低代码平台应该如何选择&#xff1f;本篇&#xff0c;我们将为大家盘点顶尖的十大低代码平…

React使报错不再白屏

如果代码中出现问题导致报错&#xff0c;通常会使页面报错&#xff0c;导致白屏 function Head() {// 此时模拟报错导致的白屏return <div>Head --- {content}</div> } export default () > {return (<><div>下面是标题</div><Head />…

Wpf 使用 Prism 实战开发Day07

待办事项页面设计 效果图: 一.布局设计 页面主要分上下布局&#xff0c;分2行进行设计&#xff0c;使用 Grid.RowDefinitions 将页面分上下2行 例如&#xff1a; <Grid.RowDefinitions><RowDefinition Height"auto"/><RowDefinition/> </Gri…