图的连通性

今天药忘吃喽~ 2021-11-10 13:26 338阅读 0赞

### 图的连通性 ###

*  无向图：割点
 *   *  源代码
 *  无向图：边双连通分量
 *  有向图:强连通分量(SCC)

# 无向图：割点 #

前言

在一个连通分量G中，对任意一个点s做DFS，能访问到所有点，产生一棵“深搜优先生成树”T。
    
    定理1：T的根结点s是割点，当且仅当s有2个或更多的子结点。
    
    定理2：T的非根结点u是割点，当且仅当u存在一个子结点v，v及其后代都没有回退边连回u的祖先

## 源代码 ##

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e3+3;
    int num[maxn];//记录DFS对每个点的访问顺序
    int low[maxn];//记录该点与该点能回到祖先的num
    // 只有low[v]>=num[u],就说明在v这条支路上没有回退边连回u的祖先，最多退到u本身
    int dfn;//代表递归的顺序
    vector<int> g[maxn];//存储图结构
    bool iscut[maxn];//标记该点是否为割点
    /* **割点**： 定理1：T的根结点s是割点，当且仅当s有2个或更多的子结点。 定理2：T的非根结点u是割点，当且仅当u存在一个子结点v，v及其后代都没有回退边连回u的祖先 */
    
    void DFS(int u,int father){ //顶点u的父节点是father
    	low[u]=num[u]=++dfn;//初始化
    	int child=0;//u 的孩子数目
    	for(int i=0;i<g[u].size();i++){ 
    		int v=g[u][i];
    		if(!num[v]){ //未访问
    			child++;
    			DFS(v,u);
    			low[u]=min(low[v],low[u]);//用后代的返回值更新
    			if(low[v]>=num[u]&&u!=1){ //定理2
    				iscut[u]=true;
    				// 若改为low[v]>num[u]&&u!=1 可求割边 （u，v)即为割边
    			}else if(num[v]<num[u]&&v!=father){ 
    				//处理回退边，father也是u的邻居，前面已访问
    				low[u]=min(num[v],low[u]);
    			}
    		}
    	}
    	if(u==1&&child>2)iscut[1]=true;
    }
    
    int main(){ 
    	int n,m;//点数，边数
    	cin>>n>>m;
    	int a,b;
    	for(int i=0;i<m;i++){ 
    		cin>>a>>b;
    		g[a].push_back(b);
    		g[b].push_back(a);
    	}
    	DFS(1,-1);//从1开始，-1表示根节点没有父节点
    	for(int i=1;i<=n;i++)if(iscut[i])printf("%d ",i);//打印割点
    }

# 无向图：边双连通分量 #

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e3+3;
    int low[maxn];//记录该点与该点能回到祖先的num
    // 只有low[v]>=num[u],就说明在v这条支路上没有回退边连回u的祖先，最多退到u本身
    int dfn;//代表递归的顺序
    vector<int> g[maxn];//存储图结构
    int n,m;//点数，边数
    
    /* **边双连通分量**： 定义：如果任意两点之间，至少存在2条“边不重复”的路径，称为“边双连通”。 性质： 边双连通图中，去掉任意一个边，图仍然是连通的。 边双连通图中没有割边。 求解： 在DFS中，所有的low值相同的点的必定在同一个边双连通分量中 */
    
    void DFS(int u,int father){ //顶点u的父节点是father
    	low[u]=++dfn;//初始化
    	for(int i=0;i<g[u].size();i++){ 
    		int v=g[u][i];
    		if(v==father)continue;//已访问
    		if(!low[i]){ 
    			DFS(v,u);
    			low[u]=min(low[u],low[v]);
    		}
    	}
    }
    
    //将low值相同的点合并，（“缩点“），求解缩点的度
    int deg[maxn];//计算每个缩点的度数
    void tarjan(){ 
    	for(int i=1;i<=n;i++){ 
    		for(int j=0;j<g[i].size();j++)if(low[i]!=low[g[i][j]])deg[low[i]]++;
    	}
    }
    
    int main(){ 
    	
    	cin>>n>>m;
    	int a,b;
    	for(int i=0;i<m;i++){ 
    		cin>>a>>b;
    		g[a].push_back(b);
    		g[b].push_back(a);
    	}
    	DFS(1,-1);//从1开始，-1表示根节点没有父节点
    	tarjan();
    	// 至少在缩点树上增加多少条边，能使这棵树变为一个边双连通图。
    	//至少增加的边数 =（总度数为1的结点数 + 1）/ 2
    }

# 有向图:强连通分量(SCC) #

#include<bits/stdc++.h>
    using namespace std;
    /* **强连通分量**。 如果一个有向图G不是强连通图，那么可以把它分成多个子图，其中每个子图的内部是强连通的， 而且这些子图已经扩展到最大，不能与子图外的任意点强连通。 称这样的一个“极大强连通”子图是G的一个强连通分量（Strongly Connected Component，SCC） */
    const int maxn = 1e3+3;
    int num[maxn];//记录DFS对每个点的访问顺序
    int low[maxn];//记录该点与该点能回到祖先的num
    // 只有low[v]>=num[u],就说明在v这条支路上没有回退边连回u的祖先，最多退到u本身
    int dfn;//代表递归的顺序
    vector<int> g[maxn];//存储图结构
    int sta[maxn],top;//栈，栈顶，处理low重复问题
    int sccno[maxn];//标记为同一个SCC
    int cnt;//SCC的个数
    int ans=0;//表示有多少对点可以相互到达的
    void DFS(int u){ 
    	sta[top++]=u;//入栈
    	num[u]=low[u]=++dfn;//初始化
    	for(int i=0;i<g[u].size();i++){ 
    		int v=g[u][i];
    		if(!num[v]){ 
    			DFS(v);//DFS的最底层，是最后一个SCC
    			low[u]=min(low[u],low[v]);
    		}else if(!sccno[v])//处理回退边
    			low[u]=min(low[u],num[v]);
    	}
    	if(low[u]==num[u]){ //栈底的点是SCC的祖先
    		cnt++;
            int x=0;//计算一个边内的点数
    		while(true){ 
    			int v = sta[--top];
    			sccno[v]=cnt;
                x++;
    			if(u==v){ 
                    ans+=x*(x-1)/2;
                    break;
                }
    		}
    	}
    }
    
    void tarjan(int n){ 
    	//....对相关参量初始化
    	for(int i=1;i<=n;i++)if(!num[i])DFS(i);
    }
    
    int main(){ 
    	int n,m;//点数，边数
        scanf("%d%d",&n,&m);
    	int a,b;
    	for(int i=0;i<m;i++){ 
    		scanf("%d%d",&a,&b);
    		g[a].push_back(b);
    	}
    	tarjan(n);//强连通图判断
        printf("%d\n",ans);
    }