请问如何求(有向/无向)图的强连通分量,还有,基础一点,怎么求有几个连通图啊

来源：学生作业帮编辑：神马作文网作业帮分类：综合作业时间：2024/11/10 12:17:51

请问如何求(有向/无向)图的强连通分量,还有,基础一点,怎么求有几个连通图啊
不太想花时间学习tarjan算法了,麻烦介绍个简单的思路,能应付复赛的时候几个数据就好了

求强连通分量的算法有tarjan和kosaraju 两种算法
相较之下 tarjan写起来比较简单 Kosaraju比较麻烦
但是想起来 Kosaraju比较简单
其他求强连通分量的算法要是还有的话估计就是需要更高深的数据结构的算法了
建议还是学下tarjan 因为他可以帮你做很多事比如求桥求割点缩环而且写起来也很简单
连通图的求法可以直接DFS 每次DFS到一个点就把它记录成已到达然后继续向下搜索每次DFS就可以求出一个连通图
附上tarjan的代码
var
next,head,point:array[1..1000] of longint;
time,tot,i,j,n,m,x,y,t:longint;
v:array[1..10000] of byte;
f,z,q:array[1..1000] of longint;
low,rea:array[1..10000] of longint;
function min(x,y:longint):longint;
begin
if x

无向连通图的连通分量! 有向图G的强连通分量是指-----,一个连通图的---是一个极小连通子图强连通图的强连通分量（连通图的连通分量）是不是就它本身设计一个算法,求无向图G(采用邻接表存储)的连通分量的个数创建一个无向图,元素为整型,以邻接矩阵为存储结构,输出该图的深度化先搜索序列,求连通分量的个数请问,图论里面的无向图是连通图的判断方法,怎么快速判断. G是一个具有n个结点的无向连通图,证明G至少有n-1条边,并证明具有n-1条边的无向连通图是一棵树图G无向连通图,G中有割点或桥,则无汉密尔顿图,怎么证明连通分量,强连通的定义是什么呢? 强连通分量.强连通图为什么2到3没有线呢设无向连通图G有n个顶点,证明G至少有（n-1）条边. 对于一个非连通无向图,共有28条边,则该图至少有多少个顶点?