图的连通性问题专题整理

全栈程序员-用户IM • 2021年12月8日下午7:00 • 未分类

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

这一篇博客继续以一些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;
}