图的连通性问题专题整理

图的连通性问题专题整理

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

   这一篇博客继续以一些OJ上的题目为载体,对图的连通性专题进行整理一下。会陆续的更新。。。


爱上大声地

一、相关定义

1、假设图G中随意两点能够相互到达。则称图G为强连通图。

2、假设图G不是强连通图,而它的子图G’是强连通图。那么称图G’为图G的强连通分量


求强连通分量主要下面三种算法:Kosaraju算法、Tarjan算法、Garbow算法。。。


二、例题

1、HDU 1269

1)使用Tarjan算法来解决

/*
 * HDU_1269_2.cpp
 *
 *  Created on: 2014年7月7日
 *      Author: pc
 */

#include <iostream>
#include <cstdio>


using namespace std;


const int maxm = 100010;//边的最大数目
const int maxn = 10005;//顶点的最大值

/**
 * 链式前向星
 */
struct node{
	int e;
	int next;
}edge[maxm];


int head[maxn];

int n,m,k;
int low[maxn];//low[v]用与保存节点v邻接的未删除的节点u的low[u]和low[v]中的最小值
int dfn[maxn];//dfn[i]用来表示节点i的訪问时间
int stack[maxn];//
int vis[maxn];//vis[i] = 1..表示节点i已经被訪问过
int cnt,index,top;//cnt: 强连通分量的个数.top:用来维护栈中的数据


/**
 * 加入�一条边的操作。。。
 * s: 边的起点
 * e: 边的终点
 */
void add(int s,int e){
	edge[k].e = e;
	edge[k].next = head[s];
	head[s] = k++;
}

/**
 * 使用tarjan算法来求强连通分量的个数
 * s: 表示要訪问的节点
 */
void tarjan(int s){
	//现骨干变量的初始化
	low[s] = dfn[s] = ++index;
	stack[++top] = s;
	vis[s] = true;


	//訪问节点s邻接的全部未删除节点e
	int i;
	for(i = head[s] ; i != -1 ; i = edge[i].next){
		int e = edge[i].e;

		if(!dfn[e]){
			tarjan(e);
			low[s] = min(low[s],low[e]);
		}else if(vis[e]){
			low[s] = min(low[s],dfn[e]);
		}
	}

	if(low[s] == dfn[s]){//表示当前节点就是一个强连通分量的根
		cnt++;

		int e;
		do{
			e = stack[top--];
			vis[e] = false;
		}while(s != e);
	}
}


/**
 * 完毕初始化的相关操作..
 */
void init(){
	memset(head,-1,sizeof(head));
	memset(dfn,0,sizeof(dfn));//素有节点被訪问的时间戳被初始化为0.表示还没有被訪问
	memset(vis,0,sizeof(vis));//一開始全部的节点被标记为未訪问过...

	cnt = 0;//cnt: 强连通分量的个数..
	index = 0;
	k = 0;//边的条数
	top = -1;// 用来维护栈中的元素
}

int main(){
	while(scanf("%d%d",&n,&m),n||m){
		init();

		int i;
		for(i = 0 ; i < m ; ++i){
			int a,b;
			scanf("%d%d",&a,&b);

			add(a,b);
		}


		for(i = 1 ; i <= n ; ++i){
			if(!dfn[i]){
				tarjan(i);
			}
		}

		if(cnt == 1){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}

	return 0;
}








版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • PyCharm最新激活码PyCharm2021.5.3有效【在线注册码/序列号/破解码】「建议收藏」

    PyCharm最新激活码PyCharm2021.5.3有效【在线注册码/序列号/破解码】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • keypad.h arduino按键操作显示

    keypad.h arduino按键操作显示#include<Keypad.h>constbyteROWS=4;//矩阵键盘行数constbyteCOLS=4;//矩阵键盘列数//按键定义charhexaKeys[ROWS][COLS]={{‘0′,’1′,’2′,’3’},{‘4′,’5′,’6′,’7’},{‘8′,’9′,’A’,’B’},{‘…

  • IDEA汉化之2021版本

    IDEA汉化之2021版本打开最新版本的IDEA后在浏览器直接进入Chinese(Simplified)LanguagePack/中文语言包-IntelliJIDEs|JetBrains,右上角,IDEA中会出现弹窗,直接起飞!

  • JAVA简历1到三年

    JAVA简历1到三年JAVA开发工程师_3年基本资料求职意向意向职位: Java开发工程师 求职地址:北京期待薪资:面议到岗时间:随时工作性质:全职 目前状况:已离职个人技能1.熟练Java语言基础语法以及面向对象特征。2.熟练Java语言中常用API的使用,如IO,String,Collection等。3.熟练MySQL的增删改查操作以及JDBC数据库连接池的使用。4.熟悉Git这种分布式版本的控制系统的使用。5.熟悉Spring、Springmvc、M

  • Microsoft store应用商店无法加载页面代码: 0x80131500

    Microsoft store应用商店无法加载页面代码: 0x80131500Microsoftstore应用商店无法加载页面代码:0x80131500出错后我在微软官网查找问题原因,以下设置都可能解决问题:原文建议先尝试更换网络连接,比如连接个人手机热点,再使用MicrosoftStore进行尝试。如果您连接了VPN或下载了第三方防火墙应用,建议断开VPN,卸载第三方防火墙应用。①调整网络连接…

  • 字符串正则匹配leetcode_动态规划100题

    字符串正则匹配leetcode_动态规划100题原题链接给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。‘.’ 匹配任意单个字符‘*’ 匹配零个或多个前面的那一个元素所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。示例 1:输入:s = “aa” p = “a”输出:false解释:”a” 无法匹配 “aa” 整个字符串。示例 2:输入:s = “aa” p = “a*”输出:true解释:因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是

发表回复

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

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