大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。
这一篇博客继续以一些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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118258.html原文链接：https://javaforall.net
