-
2021-11-22 16:10:59
●连通分量:图的极大连通子图
●强连通图:有向图中任意两个顶点都存在路径
●强连通图的连通分量是其本身
●非强连通图的连通分量不止一个
下面求一个非强连通图的所有连通分量
方法:
(1)随便找一个有向环
(2)拓展该有向环:如果某个顶点到环中的任一顶点有路径,并且该环中的任一顶点到这个顶点也有路径,则加入这个顶点
(3)最后剩下的部分就是图的连通分量
理解:
①如果在环中存在某个顶点,到待拓展顶点有路径,根据环的定义:环中任意两点都存在路径 可知,环中的所有顶点到待拓展顶点都有路径
②如果待拓展顶点到环中的某个顶点有路径,同理,根据环的定义,待拓展顶点到环中所有顶点都有路径
根据①②,可知环中所有顶点到待拓展顶点都有路径,且待拓展顶点到环中所有顶点都有路径,
根据环的定义,拓展顶点加入环中后,所得的图仍是一个环
更多相关内容 -
强连通分量
2019-08-24 15:55:17本文首先介绍了强连通分量的相关定义以及其应用范围,然后将着重介绍两种求强连通分量的算法:Kosaraju算法以及Tarjan算法,它们的时间复杂度都是O(n+m)(n:顶点数,m:边数)。 其中Kosaraju算法思想简单,操作...摘要
强连通分量常用于缩点,是图论中一个重要的知识点。本文首先介绍了强连通分量的相关定义以及其应用范围,然后将着重介绍两种求强连通分量的算法:Kosaraju算法以及Tarjan算法,它们的时间复杂度都是O(n+m)(n:顶点数,m:边数)。
其中Kosaraju算法思想简单,操作方便,易于理解与代码实现,但是性能以及拓展性上比Tarjan略逊一筹;本文将会逐一介绍这两种算法的思想以及实现步骤,最后会以例题的形式给出代码模板。相关定义
在有向图G中,如果两个顶点u,v间存在一条 u 到 v 的路径且也存在一条 v 到 u 的路径,则称这两个顶点u,v 是强连通的(strongly connected)。如果有向图G的任意两个顶点都强连通,则称G是一个强连通图。有向非强连通图的极大强连通子图,称为强连通分量(strongly connected components)。
极大强连通子图: G是一个极大强连通子图,当且仅当G是一个强连通子图且不存在另一个强连通子图G’,使得 G 是 G’ 的真子集。
强连通分量的应用
若将有向图中的强连通分量都缩为一个点,则原图会形成一个DAG(有向无环图),如图1所示:
图1:虚线部分构成一个强连通分量(图片来自ccf的博客)强连通分量的常见用途有两个:
- 有向图的缩点。
- 解决2-SAT问题。
Kosaraju 算法
Kosaraju算法的时间复杂度是O(n+m),基于两次DFS的有向图强连通子图算法。
该算法共分为三步:第一步,对原有向图G进行DFS,记录节点访问完的顺序d[i] , d[i] 表示第 i 个访问完的节点是d[i];
第二步,选择具有最晚访问完的顶点,对反向图GT 进行DFS,删除能够遍历到的顶点,这些顶点构成的一个强连通分量。
第三步,如果还有顶点没有删除,继续第二部,否则算法结束。代码实现:
见附录部分 code-1:Kosaraju算法模板(POJ2186)
Tarjan算法
Tarjan算法是 Robert Tarjan 发明的一个算法,其时间复杂度也是O(n+m),但我们之所以在掌握了Kosaraju算法后仍要学习Tarjan算法的主要原因有以下三点:
- Tarjan算法效率比Kosaraju算法高大概30%,所以Kosaraju可能会被卡常。
- Kosaraju算法利用递归实现,可能会爆栈;而Tarjan则不会(因为根本没递归)。
- Tarjan算法还可以通过拓展解决求割点、割桥以及2-SAT等问题。
实际上如果出题人有这个想法,那么就不是可能会超时,是一定会超时;不是可能会爆栈,是一定会爆栈,所以还是要掌握该算法的。
基本概念
Tarjan算法是基于对图深度优先搜索(DFS)的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个栈,回溯时可以判断栈顶到栈中的节点是否构成一个强连通分量。
我们定义DFS过程中遇到的四种边:- 树枝边:DFS时经过的边,即DFS搜索树上的边。
- 前向边:与DFS方向一致,从某个节点指向其某个子孙的边。
- 后向边:与DFS方向相反,从某个节点指向其某个祖先的边。
- 横向边:从某个节点指向搜索树中另一子树中的某节点的边。
定义DFN(u) 为节点 u 的搜索次序编号(时间戳),Low(u) 为u 或者u 的子树能够回溯到的最早的栈中节点的DFN值。
根据定义我们可以得出:
- 如果(u , v)为树枝边,u 为 v 的父节点,则 Low(u) = min{ Low(u) , Low(v) }。
- 如果(u , v)为后向边或指向栈中节点的横叉边,则Low(u) = min{ Low(u) , DFN(v) }。
当节点u的搜索过程结束后,若DFN(u) = Low(u),则以u为根的搜索子树上所有还在栈中的节点(即u和栈中在u之后的所有节点)是一个强连通分量,可退栈。通俗的说,若u为强连通分量的根,那么它的子孙中的最高最先应该就是它本身。
算法的主要过程
数组的初始化: 当首次搜索到点 u 时,DFN(u)为节点u的搜索次序编号(时间戳)。
堆栈: 将u压入堆栈。
更新Low(u):- 如果(u,v)为树枝边(v不在栈中),u为v的父节点,则Low(u) = min{Low(u) , Low(v)}。
- 如果(u,v)为后向边或者指向栈中节点的横叉边(v在栈中),则Low(u) = min{ Low(u) DFN(v)}。
- 如果u的子树已经全部遍历后Low(u) = DFS(u),则将u和栈中在u之后的所有节点 弹出栈。这些出栈的元素组成一个强连通分量。
- 继续搜索(或许会更换搜索的起点,因为整个有向图可能分为多个不连通的部分),直到所有点被遍历。
代码实现
见附录部分code-2:POJ2182(Tarjan算法)
参考资料
- 董永建,信息学竞赛一本通提高篇,福州:福建教育出版社,2018.6,155-178
- 秋叶拓哉,挑战程序设计竞赛第2版,北京:人民邮电出版社,2013.6,320-324
附录
code-1:Kosaraju算法模板(POJ2182)
求所有“红牛”总数。(红牛即所有牛的偶像)/******************************************************************* 最后修改:2019/8/15 Valenshi 使用说明: 用数组表示邻接表,分别建立了正图和反图; 只适用于节点从1~n的题型,切记若干节点编号是0~n-1会死循环! 主函数:scc(),用于求所有强连通分量,O(N+M),答案存放在kos数组。 *******************************************************************/ #include<cstdio> #include<cstring> const int N = 1e4+10; const int M = 5e4+10; int head[N],ver[M],nex[M],tot; //邻接表存放有向图 int rhead[N],rver[M],rnex[M],rtot;//存放反图 int vis[N],kos[N];//访问标记;节点所属联通分量标号 int ts[N],tc; //时间戳, dfs访问时的顺序;tc为当前"时间" void addEdge(int x,int y){ /* 建立一条从x->y的有向边 , 同时在反图添加一条从y->x的有向边*/ ver[++tot] = y,nex[tot] = head[x], head[x] = tot; rver[++rtot] = x,rnex[rtot] = rhead[y],rhead[y] = rtot; } void dfs(int x){ /*给节点x以及它的子孙打上时间戳*/ vis[x] = true; for(int i = head[x] ;i ;i = nex[i]){ int y = ver[i]; if(!vis[y]) dfs(y); } ts[++tc] = x; //第tc个回溯的是点x } void rdfs(int x,int k){ /* 找出属于第k个强连通分量的所有点 */ vis[x] = true;kos[x] = k; for(int i = rhead[x];i ;i = rnex[i]){ int y = rver[i]; if(!vis[y]) rdfs(y,k); } } int n,m; //点的个数,编号为1~n; int scc(){ /* 将原图分为若干强连通分量,并返回个数 */ memset(vis,0,sizeof vis);tc = 0; for(int i = 1;i <= n;i++) if(!vis[i]) dfs(i); memset(vis,0,sizeof vis); int k = 0; for(int i = tc;i > 0;i--) if(!vis[ts[i]]) rdfs(ts[i],++k); return k; } /*********************************** 以下为POJ2186解题代码 ***********************************/ int A[N],B[N]; void solve(){ int k = scc(); //备选答案总数 int y = 0,sum = 0; for(int i = 1;i <= n;i++){ if(kos[i] == k){ y = i;sum++; } } //检查是否从所有点可达 memset(vis,0,sizeof vis); rdfs(y,0); //代码重用 for(int i = 1;i <= n;i++){ if(!vis[i]){ sum = 0;break; } } printf("%d\n",sum); } int main(){ scanf("%d%d",&n,&m); for(int i = 1,x,y;i <= m;i++){ scanf("%d%d",&x,&y); addEdge(x,y); } solve(); return 0; }
code-2:POJ2182(Tarjan算法模板)
/*************************************************************** 最后更新:2019/8/16 ValenShi 使用说明: 1.记得初始化辅助数组dfn[],co[],head[], 以及"数组指针" ,top,tot,num,col ; 2.每个辅助数组具体作用见注释; 3.节点范围是1~n,若是0~n-1会死循环,可更改head[]初始值解决。 ***************************************************************/ #include<cstdio> #include<iostream> using namespace std; const int N = 1e4+10; const int M = 1e5+10; /* 邻接表存有向图 */ int head[N],ver[M],nex[M],tot; inline void addEdge(int x,int y){ ver[++tot] = y,nex[tot] = head[x],head[x] = tot; } /***************************************** Tarjan算法及其辅助数组: Stack[]为栈,top为栈顶指针; dfn[]为节点的时间戳,num为对应的"时间"; co[]为节点所在的强连通分量的编号,col对应编号; ******************************************/ int n,m; int Stack[N],top; int dfn[N],low[N],num,co[N],col; void Tarjan(int u){ dfn[u] = low[u] = ++num; Stack[++top] = u; for(int i = head[u];i ;i = nex[i]){ int v = ver[i]; if(!dfn[v]){ Tarjan(v); low[u] = min(low[u],low[v]); }else if(!co[v]) low[u] = min(low[u],dfn[v]); } if(low[u] == dfn[u]){ co[u] = ++col; while(Stack[top] != u){ co[Stack[top]] = col; top--; } top--; } } int chudu[N];/*用来记录每个强连通分量的出度 */ void solve(){ num = col = top = 0; // memset(dfn,0,sizeof dfn); // memset(co,0,sizeof co); // memset(chudu,0,sizeof chudu); for(int i = 1;i <= n;i++) if(!dfn[i]) Tarjan(i); int ans = 0,tcnt = 0; /*ans存放答案,tcnt表示出度为0的强连通分量的个数*/ for(int i = 1;i <= n;i++){ for(int j = head[i];j ;j = nex[j]){ int y = ver[j]; if(co[i] != co[y]) chudu[co[i]]++; /*i所在的强连通分量的出度+1 */ } } int tcol = 1;/*tcol为出度为0的强连通分量的编号*/ for(int i = 1;i <= col;i++) if(!chudu[i]) tcnt++,tcol = i; for(int i = 1;i <= n;i++) if(co[i] == tcol) ans++; if(tcnt > 1) puts("0"); else printf("%d\n",ans); } int main(){ scanf("%d%d",&n,&m); for(int i = 1,u,v;i <= m;i++){ scanf("%d%d",&u,&v); addEdge(u,v); } solve(); return 0; }
-
Tarjan算法求强连通分量
2018-02-03 14:15:21使用Tarjan算法进行快速计算强连通分量,C++语言实现。 -
寻找强连通分量的Tarjan算法
2020-07-01 20:28:20有向图的强连通分量 在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通...有向图的强连通分量
在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。
下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。
直接根据定义,用双向遍历取交集的方法求强连通分量,时间复杂度为O(N^2+M)。更好的方法是Kosaraju算法或Tarjan算法,两者的时间复杂度都是O(N+M)。本文介绍的是在实践中略胜一筹的Tarjan算法。
Tarjan算法
Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
定义DFN(u)为节点u搜索的次序编号(时间戳),Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出:
Low(u)=Min { DFN(u), Low(v),(u,v)为树枝边,u为v的父节点 DFN(v),(u,v)为指向栈中节点的后向边(非横叉边) }
当DFN(u)=Low(u)时,以u为根的搜索子树上所有节点是一个强连通分量。
算法伪代码如下:
tarjan(u) { DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值 Stack.push(u) // 将节点u压入栈中 for each (u, v) in E // 枚举每一条边 if (v is not visted) // 如果节点v未被访问过 tarjan(v) // 继续向下找 Low[u] = min(Low[u], Low[v]) else if (v in S) // 如果节点v还在栈内 Low[u] = min(Low[u], DFN[v]) if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根 repeat v = S.pop // 将v退栈,为该强连通分量中一个顶点 print v until (u== v) }
接下来是对算法流程的演示。
从节点1开始DFS,把遍历到的节点加入栈中。搜索到节点u=6时,DFN[6]=LOW[6],找到了一个强连通分量。退栈到u=v为止,{6}为一个强连通分量。
返回节点5,发现DFN[5]=LOW[5],退栈后{5}为一个强连通分量。
返回节点3,继续搜索到节点4,把4加入堆栈。发现节点4向节点1有后向边,节点1还在栈中,所以LOW[4]=1。节点6已经出栈,(4,6)是横叉边,返回3,(3,4)为树枝边,所以LOW[3]=LOW[4]=1。
继续回到节点1,最后访问节点2。访问边(2,4),4还在栈中,所以LOW[2]=DFN[4]=5。返回1后,发现DFN[1]=LOW[1],把栈中节点全部取出,组成一个连通分量{1,3,4,2}。
至此,算法结束。经过该算法,求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。
可以发现,运行Tarjan算法的过程中,每个顶点都被访问了一次,且只进出了一次堆栈,每条边也只被访问了一次,所以该算法的时间复杂度为O(N+M)。
求有向图的强连通分量还有一个强有力的算法,为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法,其时间复杂度也是O(N+M)。与Trajan算法相比,Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS,不用建立逆图,更简洁。在实际的测试中,Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外,该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法,也有助于深入理解求双连通分量的Tarjan算法,两者可以类比、组合理解。
求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先的离线Tarjan算法,在此对Tarjan表示崇高的敬意。
tarjan算法的C++实现
void tarjan(int i) { int j; DFN[i]=LOW[i]=++Dindex; instack[i]=true; Stap[++Stop]=i; for (edge *e=V[i];e;e=e->next) { j=e->t; if (!DFN[j]) { tarjan(j); if (LOW[j]<LOW[i]) LOW[i]=LOW[j]; } else if (instack[j] && DFN[j]<LOW[i]) LOW[i]=DFN[j]; } if (DFN[i]==LOW[i]) { Bcnt++; do { j=Stap[Stop--]; instack[j]=false; Belong[j]=Bcnt; } while (j!=i); } } void solve() { int i; Stop=Bcnt=Dindex=0; memset(DFN,0,sizeof(DFN)); for (i=1;i<=N;i++) if (!DFN[i]) tarjan(i); }
-
图论学习-有向图强连通分量
2022-02-04 16:10:05文章目录有向图强连通分量1.定义:2.基本术语与概念2.1 边的概念2.2 缩点2.3 时间戳3. tarjan求强连通分量(SCC)3.1 原理3.2 步骤3.3 模板3.3.1 tarjan求强连通分量的过程3.3.2 缩点的过程4.例题题目1:P2341 ...文章目录
有向图强连通分量
1.定义:
给定一张有向图,若对于图中任意两个节点x,y,既存在从x到y的路径,也存在y到x的路径,则该有向图是强连通图。
有向图的极大强连通子图被称为:强连通分量,简称SCC(Strongly connected component)
Tarjan 算法基于dfs,可以在线性时间内求出一张有向图的所有连通分量。2.基本术语与概念
2.1 边的概念
1.树枝边:搜索树中给定两个点x,y,x是y的父亲节点,那么这条边就是树枝边
2.前向边:搜索树中给定两个点x,y,x是y的祖先节点,那么这条边就是前向边
3.后向边:搜索树中给定两个点x,y,y是x的祖先节点,那么这条边就是后向边
4.横叉边:搜索树中给定两个点x,y,不属于以上三种的边,就叫横叉边,且y在搜索树中的编号一定小于x在搜索树中的编号。即dfn[y]<dfn[x],(连向其他搜索过的节点的边),可以发现:往左边的横叉边是横叉边,往右边的横叉边实际上是树枝边,因为右边的节点还没有被搜过。
举个例子:
dfn数组存储的即是各个深度优先遍历过程中,每个节点第一次被访问的时间顺序,读者不妨对该图做一次深度优先遍历加以验证。
例如:1,2即是树枝边,注意:树枝边一定也是前向边
1,8即是前向边,4,6即是后向边,8,7是横叉边
2.2 缩点
将所有连通分量缩成一个点。
2.3 时间戳
在搜索的时候,按照深度优先遍历顺序给每个点一个编号,即时间戳。
dfn[u]表示遍历到u的时间戳。3. tarjan求强连通分量(SCC)
3.1 原理
- 把边分成四大类:树枝边,前向边,后向边,横叉边
- 取一个点x,判断它是否在强连通分量中
情况1:存在一条后向边使得它可以走到某个祖先节点
情况2:存在一条横叉边,它先通过横叉边,然后横叉边所在的点可以走到某个祖先节点
以上两种情况,点x和它的祖先节点之间所有节点都可以互相到达,满足强连通分量的定义。
3.2 步骤
- 给每个点定义两个时间戳:
dfn[u]表示遍历到u的时间戳,即dfs的搜索顺序
low[u]表示从u开始走,所能遍历到的最小时间戳 - u是其所在强连通分量的最高点,等价于dfn[u]==low[u]
3.3 模板
3.3.1 tarjan求强连通分量的过程
void tarjan(int u) { dfn[u] = low[u] = ++timestamp;//时间戳 stk[++top] = u,in_stk[u] = true;//把当前点放到栈里面去,随后标记u已经入栈 for(int i = h[u];~i;i = ne[i]) { int j = e[i]; if(!dfn[j]) { tarjan(j);//先看一下u能到的点 //这里做完tarjan(j)以后,low[j]已经被更新了,由定义可知,low[j]保存的就是从j出发能到达的时间戳最小的点 low[u] = min(low[u],low[j]);//更新low[u] } else if(in_stk[j]) { //可能通过其他边能搜到j,但不是当前分支搜到的,读者这里可以好好考虑考虑 //stk不一定只存了当前分支的点,还可能存有前面其他分支的点,比如横叉边所到达的点 //stk存的是当前还没有遍历完的强连通分量的所有点 low[u] = min(low[u],dfn[j]); } } if(dfn[u]==low[u]) { //u必然是u所在的强连通分量的最高点(由定义) int y; ++scc_cnt; do{ y = stk[top--];//把栈顶弹出 in_stk[y] = false;//标记它没有在栈里面 id[y] = scc_cnt;//标记y这个点属于scc_cnt这个强连通分量 }while(y!=u); } } // y总原话:《最好背过》 :)
3.3.2 缩点的过程
for(int i = 1;i<=n;i++) { for(i的所有邻点j) { if(i和j不在同一个强连通分量中) { 把i所在的强连通分量向j所在的强连通分量加一条边; } } } //缩完点就是DAG(有向无环图)
注:缩完点以后,连通分量编号递减的顺序一定是拓扑序
给出注的证明:
对于一个图做一遍深度优先遍历,把每个点加入序列seq中
显然有seq的逆序即是拓扑序。for(int i = h[u];~i;i = ne[i]) { int j = e[i]; if(!st[j]) { seq<-j;//把j存入seq序列中 dfs(j); } } //读者不妨验证一下
最后,观察tarjan求有向图强连通分量的过程实际上就是对图做深度优先遍历的过程,所以最后按连通分量编号递减的顺序输出一定是拓扑序
4.例题
题目1:P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G
一个思路是建反图,对每个奶牛做一遍dfs,统计完美奶牛个数,时间复杂度O(nm),显然超时。
再观察:
题意知当是有向无环图时,只要有两个点出度为0,那么完美奶牛个数为0,如果有一个出度为0,那么完美奶牛个数为1,
于是可以tarjan缩点,如果只有一个出度为0的强连通分量,那么答案就是该强连通分量的size。#include<bits/stdc++.h> using namespace std; const int N = 1e4+10,M = 5e4+10; int n,m; int h[N], e[M], ne[M], idx; int dfn[N], low[N], timestamp; // 时间戳 int stk[N], top; bool in_stk[N]; int id[N], scc_cnt; // 每个点所属分量编号 int dout[N],sz[N];//出度数组 void add(int a,int b) { e[idx] = b,ne[idx] = h[a],h[a] = idx++; } void tarjan(int u) {//缩点 dfn[u] = low[u] = ++timestamp; stk[++top] = u,in_stk[u] = true; for(int i = h[u];~i;i = ne[i]) { int j = e[i]; if(!dfn[j]) { tarjan(j); low[u] = min(low[u],low[j]); } else if(in_stk[j]) { low[u] = min(low[u],dfn[j]); } } if(dfn[u]==low[u]) { ++scc_cnt; int y; do{ y = stk[top--]; in_stk[y] = false; id[y] = scc_cnt; sz[scc_cnt]++; }while(y!=u); } } int main() { memset(h, -1, sizeof h); cin>>n>>m; while (m -- ){ int a,b; cin>>a>>b; add(a, b); } for(int i = 1;i<=n;i++) { if(!dfn[i]) { tarjan(i); } } for(int i = 1;i<=n;i++) { for(int j = h[i];~j;j = ne[j]) { int k = e[j]; int a = id[i],b = id[k]; if(a!=b) { //说明i和j不在同一个连通分量中 dout[a]++;//这里没有实际把边加出来,因为不在同一个连通分量中,所以要把a的出度+1,等价于加了一条边 } } } int sum = 0,zeros = 0;//zeros记录出度为0的连通分量的个数 for(int i = 1;i<=scc_cnt;i++) { if(!dout[i]) { zeros++; sum+=sz[i]; if(zeros>1) { cout<<0; return 0; } } } cout<<sum; return 0; }
题目2:P2746 [USACO5.3]校园网Network of Schools
第一个问类似题目1,第二个问需要找小性质:如何让有向无环图变成强连通图添加的边的数量最少?
设 a 为 入 度 为 0 的 点 的 个 数 , b 为 出 度 为 0 的 点 的 个 数 那 么 易 有 a n s = m a x ( a , b ) 设a为入度为0的点的个数,b为出度为0的点的个数\\ 那么易有ans = max(a,b) 设a为入度为0的点的个数,b为出度为0的点的个数那么易有ans=max(a,b)
题解来自《算法竞赛进阶指南》:
AC code:#include<bits/stdc++.h> using namespace std; const int N = 1e4+10,M = 5e4+10; int n,m; int h[N], e[M], ne[M], idx; int dfn[N], low[N], timestamp; // 时间戳 int stk[N], top; bool in_stk[N]; int id[N], scc_cnt; // 每个点所属分量编号 int dout[N],sz[N],din[N];//出度数组 void add(int a,int b) { e[idx] = b,ne[idx] = h[a],h[a] = idx++; } void tarjan(int u) {//缩点 dfn[u] = low[u] = ++timestamp; stk[++top] = u,in_stk[u] = true; for(int i = h[u];~i;i = ne[i]) { int j = e[i]; if(!dfn[j]) { tarjan(j); low[u] = min(low[u],low[j]); } else if(in_stk[j]) { low[u] = min(low[u],dfn[j]); } } if(dfn[u]==low[u]) { ++scc_cnt; int y; do{ y = stk[top--]; in_stk[y] = false; id[y] = scc_cnt; sz[scc_cnt]++; }while(y!=u); } } int main() { memset(h, -1, sizeof h); cin>>n; for(int i = 1;i<=n;i++) { int x; while(cin>>x,x) { add(i,x); } } for(int i = 1;i<=n;i++) { if(!dfn[i]) { tarjan(i); } } for(int i = 1;i<=n;i++) { for(int j = h[i];~j;j = ne[j]) { int k = e[j]; int a = id[i],b = id[k]; if(a!=b) { //说明i和j不在同一个连通分量中 dout[a]++;//这里没有实际把边加出来,因为不在同一个连通分量中,所以要把a的出度+1,等价于加了一条边 din[b]++; } } } int sum1 = 0,sum2 = 0,cnt1 = 0,cnt2 = 0; //cnt1记录出度为0的连通分量的个数 //cnt2记录入度为0的连通分量的个数 for(int i = 1;i<=scc_cnt;i++) { if(!dout[i]) { cnt1++; } if(!din[i]) { cnt2++; } } if(scc_cnt!=1) cout<<cnt2<<endl<<max(cnt1,cnt2); else cout<<cnt2<<endl<<"0"; return 0; }
陆续更新~
5.参考资料
- acwing算法提高课图论
- 《算法竞赛进阶指南》
-
算法竞赛——强连通分量
2022-03-20 11:09:44强连通分量(Strongly Connected Components,SCC)的定义是:极大的强连通子图也可以说,在强连图图的基础上加入一些点和路径,使得当前的图不在强连通,称原来的强连通的部分为强连通分量。 DFS生成树 DFS生成树... -
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
2022-06-13 20:04:33如果 G 是有向图,那么连接 i 和 j 的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。如果此图是有向图,则称为...今天叶子为大家分享的是【连通图、连通分量与强连通图、强连通分量】... -
Tarjan找强连通分量
2019-11-07 11:27:10如果一张图的某个子图为强连通图,则称其为强连通分量。 算法思路 该算法主要用于有向图。对于每一个点,赋予两个属性:dfn和low。dnf记录该点被访问的次序。low记录与该点联通的所有点的dfn的最小值。对访问每一... -
Python 计算两个连通子图距离_[图论] Tarjan算法-找强连通分量
2020-11-21 12:38:14Tarjan算法可以解决强连通分量、双连通分量、割点和桥、LCA等问题,这里介绍用它来找强连通分量。有向图:由有向边构成的图,与之对应的是无向图。强连通分量:如果两个顶点可以相互到达,则称两个顶点强连通... -
有向图的强连通分量课程设计报告.docx
2021-07-05 15:29:43有向图的强连通分量课程设计报告 -
tarjan(e):Tarjan 的强连通分量算法-matlab开发
2021-05-30 02:25:22实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了... -
强连通分量个数的求法(图解)
2020-09-27 01:30:11强连通分量个数的求法(图解) 背景 最近刷软考题的时候,碰到2013年上半年软件设计师的第31题,求程序图的环路复杂度。答案解析中有这么一段话: 根据图论,在一个强连通的有向图G中,环的个数V(G)由以下公式给出... -
强连通分量函数.c
2021-12-12 03:02:15强连通分量函数.c -
数据结构课程设计报告--实现求有向图强连通分量的算法
2018-06-22 15:01:33在键盘上输入有向图,对任意给定的图(顶点数和边数自定),建立它的邻接表并输出。然后判断该图是否强连通。如果是强连通图,求出该图的所有强连通分量并输出字符 -
求强连通分量(拓扑排序)的两种算法
2020-07-20 23:14:06强连通分量分解,拓扑排序 两遍dfs tarjian算法 两遍dfs dfs后序遍历,此时标号最大的是头部(也就是开始搜索的根部) 将边反向后,根据强连通分量的性质,边反向后对强连通分量无影响,分量内各个点之间仍然相互可... -
连通分量、强连通分量与Tarjan算法
2022-03-23 15:42:07即一个连通分量加上任何一些点之后它都不是一个连通分量,那么就把它称为强连通分量。 求强连通分量的意义在于能够把任意一个有向图经过缩点之后转化成一个有向无环图(DAG图),缩点是指将所有强连通分量缩成一个点... -
强连通分量求解算法
2018-10-23 20:32:14强连通分量 在有向图中,如果顶点v和w相互可达,则称这两个顶点之间强连通。一幅图中任意两点之间强连通则称这幅图为强连通图。有向图的极大强连通子图就是有向图的强连通分量(Strongly Conneted Component)。 ... -
强连通分量(Tarjan算法) 图解
2022-03-01 16:16:43强连通分量(scc):图 G G G 不是一个强连通图,但其子图 G ′ G^\prime G′ 是 G G G 的最大强连通子图,则称 G ′ G^\prime G′ 为一个强连通分量 tarjan算法就是一个可以找出图中所有强连通分量的方法。... -
强连通分量——tarjan算法缩点
2022-05-18 18:19:28一. 什么是强连通分量? 强连通分量:在有向图G中,如果两个顶点u,v间(u->...在强连图图的基础上加入一些点和路径,使得当前的图不在强连通,称原来的强连通的部分为强连通分量。 二. 强连通分 -
图的连通,连通图,连通分量,强连通分量
2020-11-21 18:55:421.对于无向图而言,如果图中的某两个点,例如:存在W到V的路径,那么我们说w和v是连通的;进一步如果图中任意两点之间都是存在路径的,那么我们说这个是连通的,即可称为连通图。 2.连通子图:设G=(V,E)和G`=(V`,E`... -
Tarjan求强连通分量【模板】.cpp
2021-04-14 23:51:23纯代码 -
图论算法-Tarjan之强连通分量
2022-01-18 14:04:10Tarjan--强连通分量 -
强连通分量分解详解 超级详细
2021-11-04 23:28:59其次我们得了解,什么是强连通分量? 最后我们得了解,什么是强连通分量? #include <iostream> #include <stdio.h> #include <vector> #include <string.h> using namespace std; vector&... -
【教程】连通分量、强连通分量以及双连通分量
2019-08-16 14:42:37强连通分量是有向图相关 关于连通分量 连通分量的定义 无向图中的一个点集,点集中的任意一对点都可以互相到达,且点集外的点与点集中任意一点都不能互相到达。 举个栗例子 这个无向图中存在一个连通分量(显然任意... -
有向图的强连通分量
2021-09-20 20:47:41而一个有向图中的极大强连通子图就被称为强连通分量。(极大强连通子图就是指一个强连通子图,再加入任何额外的节点都无法保证这个新的图是一个强连通图) 举个例子: 显然这个图里两个点集[1,3,5][1,3, 5][1,3,5]和 ... -
强连通分量(方法)
2017-05-06 20:45:05求强连通分量的方法: 第一种Kosaraju算法: (1)第一次对图G进行dfs遍历,并在遍历过程中,记录每一个点的退出顺序 如果以1为起点遍历,访问结点的顺序如下: 1 2 3 5 5 3 2 1 4 4 1 结点第二次... -
实现有向图强连通分量的算法-数据结构课程设计报告x_数据结构有向图的邻接链表
2020-02-18 10:13:32课 程 设 计 报 告 课程设计名称数据结构课程设计 课程设计题目实现求有向图强连通分量的算法 院系 专 班 学 姓 业 级 号 名 指导教师 沈阳航空航天大学课程设计报告 目 录 系 统 分 析 .1 1.1 题 目 介 绍 .1 1.2 ... -
实验_C++_数据结构_图连通分量_
2021-10-03 18:16:11用邻接表存储结构,编写一个求无向图的连通分量个数的算法。