圖的連通性

LINNO 2021-08-15 17:54:15 阅读数:74

本文一共[544]字,预计阅读时长:1分钟~
通性
title : 圖的連通性
date : 2021-8-10
tags : ACM,圖論,連通性

 

强連通分量(SCC)

有向圖强連通分量:在有向圖G中,如果兩個頂點vi,vj間(vi>vj)有一條從vi到vj的有向路徑,同時還有一條從vj到vi的有向路徑,則稱兩個頂點强連通(strongly connected)。如果有向圖G的每兩個頂點都强連通,稱G是一個强連通圖。有向圖的極大强連通子圖,稱為强連通分量。

縮點

將有向有環圖中的環縮成一個個點,形成一個有向無環圖。

第一步是要找環,使用tarjan算法dfs遍曆整個圖,用棧來保存當前所在路徑上的所有點,一旦無法往下走就退棧並增加連通分量。

//luoguP3387 【模板】縮點
#include<bits/stdc++.h>
using namespace std;

const int maxn=10005;
int n,m,u,v,a[maxn];
int tot,head[maxn];//tot,head用於鏈式前向星
int idx,bel[maxn],dfn[maxn],low[maxn];
//idx為當前時間戳,bel為連通分量,dfn為點的訪問時間,low(u)為分量最早的訪問時間
int stk[maxn],top,vis[maxn]; //stk為手寫棧,top為棧頂,vis標記訪問
int ru[maxn],dist[maxn];
//ru為入度,dist[i]為以i為終點的最大點權

struct E{
int to,next,from;
}e[maxn*10];

vector<int>G[maxn]; //存放縮點後的圖,便於區分

void addedge(int x,int y){ //鏈式前向星建初始圖
e[++tot].next=head[x];
e[tot].from=x;
e[tot].to=y;
head[x]=tot;
}

void tarjan(int x){
low[x]=dfn[x]=++idx; //時間戳和最早時間
stk[++top]=x; //入棧
vis[x]=1;//標記已經訪問
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(!dfn[v]){ //如果沒訪問過下一個節點
tarjan(v); //訪問下一個節點
low[x]=min(low[x],low[v]); //如果形成環,承接下一個節點的最早時間
}else if(vis[v]){ //如果已經訪問過下一個節點
low[x]=min(low[x],low[v]); //這貌似是有爭議的地方
}
}
if(dfn[x]==low[x]){ //x是一個連通分量
int y;
while(y=stk[top--]){ //訪問的元素出棧
bel[y]=x; //y屬於連通分量x
vis[y]=0; //這句話少了就50分,想一想蝴蝶結的情况就知道啦
if(x==y) break;
a[x]+=a[y]; //在本題中縮點後把點權相加
}
}
}

int topo(){ //拓撲排序
queue<int>q;
for(int i=1;i<=n;i++){
if(bel[i]==i&&!ru[i]){ //如果該點是連通分量並且入度為0
q.push(i);
dist[i]=a[i]; //記錄該點為終點的點權之和
}
}
while(!q.empty()){
int fro=q.front();q.pop();
for(int i=0;i<G[fro].size();i++){
int to=G[fro][i];
dist[to]=max(dist[to],dist[fro]+a[to]);
ru[to]--;
if(!ru[to]) q.push(to); //入度為0的點入隊
}
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,dist[i]); //記錄答案
return ans;
}

signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++){
cin>>u>>v;
addedge(u,v); //建單向邊
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i); //tarjan縮點
}
for(int i=1;i<=m;i++){ //對於每條邊
int x=bel[e[i].from],y=bel[e[i].to];
if(x!=y){ //如果處於不同的連通分量,則建邊
G[x].push_back(y);
ru[y]++;
}
}
printf("%d",topo());
return 0;
}
割點

無向連通圖中,某點和連接點的邊去掉後,圖不再連通。

在tarjan中,對於某一個頂點u,如果存在至少一個頂點v(u的兒子),使得low[v]>=dfn[u],即不能回到祖先,那麼u點為割點。

判斷割點的兩個條件:

①x是根節點並且度數>1

②x不是根節點並且dfn[x]<=low[y],y為x的兒子

void tarjan(int x){ //求割點
   dfn[x]=low[x]=++num;
   int col=0;
   for(int i=head[x];i;i=e[i].next){
       int y=e[i].to;
       if(!dfn[y]){
           col++;
           tarjan(y);
           low[x]=min(low[x],low[y]);
           if((x==root&&col>1)||(x!=root&&dfn[x]<=low[y]))
               is[x]=1;//這個點是割點
      }else low[x]=min(low[x],dfn[y]);
  }
}
橋(割邊)

無向連通圖中,去掉一條邊,圖中的連通分量數增加,則這條邊,稱為橋或者割邊。

void tarjan(int x){ //求橋
   dfn[x]=low[x]=++idx;
   for(int i=head[x];i;i=e[i].next){
       if(i==f[x]^1) continue;//反向邊跳過
       int v=e[i].to;
if(!dfn[v]){
           f[v]=i;
           tarjan(v);
           low[x]=min(low[x],low[v]);
           if(low[v]>dfn[x]) ans++,cut[i]=cut[i^1]=1;//橋
      }else low[x]=min(low[x],dfn[v]);
  }
}

 

 

雙連通分量(BCC)

邊雙連通

若一個無向圖中的去掉任意一條邊都不會改變此圖的連通性,即不存在橋,則稱作邊雙連通圖。

點雙連通

若一個無向圖中的去掉任意一個節點都不會改變此圖的連通性,即不存在割點,則稱作點雙連通圖。

 

參考資料

https://blog.csdn.net/acmmmm/article/details/16361033

https://www.luogu.com.cn/blog/juruohyfhaha/post-ti-xie-su-dian

https://www.cnblogs.com/ljy-endl/p/11595161.html

版权声明:本文为[LINNO]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815175349228l.html