大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
这一篇博客继续以一些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账号...