强连通(strongly connected): 在一个有向图G里,设两个点 a b
发现,由a有一条路可以走到b,由b又有一条路可以走到a,我们就叫这两个顶点(a,b)强连通。

强连通图: 如果 在一个有向图G中,每两个点都强连通,我们就叫这个图,强连通图。


强连通分量strongly connected components):在一个有向图G中,有一个子图,这个子图每2个点都满足强连通,我们就叫这个子图叫做
强连通分量 。



有向图的缩点就是把有向图中强连通分量缩成一个点(道理很简单,我到了这个强连通分量的任何一点,那么这个强连通分量就能被我访问了),在处理有向图的连通性问题时有很多作用。

比如如下问题:

给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图,

输出一个尽可能小的点集,使得从这些点出发能够到达任意一点,如果有多个这样的集合,输出这些集合升序排序后字典序最小的。

第一行为两个整数 1 ≤ n, m ≤ 105,
接下来 M 行,每行两个整数 1 ≤ u, v ≤ 105 表示从点 u 至点 v 有一条有向边。


数据保证没有重边、自环。

第一行输出一个整数 z,表示作为答案的点集的大小;


第二行输出 z 个整数,升序排序,表示作为答案的点集。


7 10 4 5 5 1 2 5 6 5 7 2 4 2 1 2 5 3 3 5 3 62 4 7

不明白缩点的话,是很难做出来的,也有其他方法,这里这是举个例子来解决问题。

缩点其实难在求有向图的强连通分量上面,这个得先去了解一下点击打开链接
<https://blog.csdn.net/wust_cyl/article/details/80036555>

我们把输出的代码改一下,记录到一个数组里面并且同时给每一个点打上标记,即这些点都是一个强连通分量里面的

num记录的是强连通分量数量,p是记录第几个强连通分量里面的点,unicom表示每一个点属于第几个强连通分量。


算法复杂度O(N+E)

这样我们的预备工作就做好了。把N个点划分成了num个强连通分量块了。

问了验证有向图的联通性,我们还需要利用边的信息。


假如存a->b的边而且unicom[a]!=unicom[b]即它们俩个点不属于同一强连通分量。那么也就是说我们到达了点a,那么包括点b的强连通分量就全部可以到达了。

我们给强连通分量unicom[b]打上标记,这块不用考虑了,考虑a就行了。

S数组保存起点 E数组保存终点  e表示边的条数。


算法复杂度O(E)

总时间复杂度O(E+N)

基本上这个连通性的问题就解决了,对于那些没有打上标记的强连通分量就需要选取到达了。

代码如下:
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+100;
vector<int> G[maxn],p[maxn],ans; int
low[maxn],dfn[maxn],Stack[maxn],S[maxn],E[maxn],n,e,cnt,Index,num; int
link[maxn],unicom[maxn]; bool vis[maxn]; void tarjan(int u) {
low[u]=dfn[u]=++cnt; vis[u]=true; Stack[++Index]=u; for (int
i=0;i<G[u].size();i++) { int v=G[u][i]; if (!dfn[v]) { tarjan(v);
low[u]=min(low[u],low[v]); } else if (vis[v]){ low[u]=min(low[u],dfn[v]); } }
if (dfn[u]==low[u]) { ++num; do { p[num].push_back(Stack[Index]);
unicom[Stack[Index]]=num; vis[Stack[Index]]=false; Index--; }while
(u!=Stack[Index+1]); } return ; } int main() { scanf("%d%d",&n,&e); for (int
i=1;i<=e;i++) { scanf("%d%d",&S[i],&E[i]); G[S[i]].push_back(E[i]); } memset
(vis,false,sizeof(vis)); for (int i=1;i<=n;i++) { if (!dfn[i]) tarjan(i); } for
(int i=1;i<=e;i++) { if (unicom[S[i]]!=unicom[E[i]]) link[unicom[E[i]]]=1; }
for (int i=1;i<=num;i++) sort(p[i].begin(),p[i].end()); for (int
i=1;i<=num;i++) { if (!link[i]) ans.push_back(p[i][0]);//选取第一个点就好了 }
sort(ans.begin(),ans.end()); printf("%d\n",ans.size()); for (int
i=0;i<ans.size();i++) { printf("%d%c",ans[i],(i==ans.size()-1)?'\n':' '); }
return 0; }
























友情链接
ioDraw流程图
API参考文档
OK工具箱
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:637538335
关注微信