圖的連通性

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