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