連通性

無向圖的聯通分量

割點:在一個聯通分量里面有一些關鍵點,如果刪除它,會把這個聯通分量分為更多。 割邊——雙連通問題

有多少個割點:DFS,深搜優先生成樹

對任意一個點s做DFS,生成一棵樹

1)如果樹的根節點s有兩個或更多的孩子:s是割點

2)T的非根節點u是割點:當且僅當u存在一個子節點v,v及其后代都沒有回退邊連回u的祖先

HOW:u的直接后代v,數組num[]表示DFS時候的順序,low[i]表示i及其后代能夠回退回的祖先的num,一開始是num[i]=low[i]=dfn++

如果low[v]>=num[u],那么u就是割點

如果low[v]>num[u],那么u-->v就是割邊

int low[maxn],num[maxn];vector<int> g[maxn];bool iscut[maxn];int dfn;void dfs(int u,int fa){low[u]=num[u]=dfn++;  //初始值為DFS訪問的順序int child=0;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[u],low[v]);   //用后代的Low更新爸爸的lowif(low[v]>=num[u]&&u!=1) //判斷割點1:不是根節點的判斷 iscut[u]=1; }else if(num[v]<num[u]&&v!=fa){low[u]=min(low[u],num[v]); //處理回退邊,fa也是u的鄰居,但是之前已經訪問過,所以不需要處理 }}if(u==1&&child>=2) iscut[1]=1; //根節點 }int main(){int ans,n;//輸入圖memset(low,0,sizeof(low));memset(num,0,sizeof(num));dfn=0;memset(iscut,0,sizeof(iscut));ans=0;dfs(1,-1);for(int i=1;i<=n;i++) ans+=iscut[i];cout<<ans<<endl;return 0;}

雙連通分量:

在一個聯通圖中任選兩點,如果至少存在兩條“點不重復”的路徑,成為點雙連通,點雙連通極大子圖:點雙連通分量(沒有割點)

邊雙連通分量:沒有割邊

點雙連通分量:Tarjan,在dfs的時候,把遍歷過程中的點保存起來,就可以得到點雙連通分量,保存在棧,找到割點就拿出來,注意存在棧的是邊

邊雙連通分量:縮點的技術:

1)首先找出圖G的所有邊雙連通分量,DFS時,所有點生成low值,low值相同的就是同一個SCC,,有多少個SCC就有多少個邊雙連通分量

2)把每個邊雙連通分量看作一個點,low值相同的合并為一個點

3)轉化為一棵樹,即至少在縮點樹上面增加多少條邊才能變為一個邊雙連通圖,即(度為1的點+1)/2

下面的是求需要連接多少條邊才能變為雙連通分量,只需要low數組

#include<iostream>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<cstdio>#include<queue>#include<map>#include<vector>#include<set>using namespace std;const int maxn=1010;const int INF=0x3fffffff;typedef long long LL;int n,m,low[maxn],dfn;vector<int> g[maxn]; void dfs(int u,int fa){low[u]=++dfn;for(int i=0;i<g[u].size();i++){int v=g[u][i];if(v==fa) continue;if(!low[v]) dfs(v,u);low[u]=min(low[u],low[v]);}}int degree[maxn]; //計算每個縮點的度數 int tarjan(){memset(degree,0,sizeof(degree));for(int i=1;i<=n;i++){for(int j=0;j<g[i].size();j++){if(low[i]!=low[g[i][j]]){degree[low[i]]++;}}} int res=0;for(int i=1;i<=n;i++){if(degree[i]==1) res++;}return res;}int main(){while(~scanf("%d %d",&n,&m)){memset(low,0,sizeof(low));for(int i=0;i<=n;i++) g[i].clear();for(int i=1;i<=m;i++){int a,b;scanf("%d %d",&a,&b);g[a].push_back(b);g[b].push_back(a);}dfn=0;dfs(1,-1);int ans=tarjan();printf("%d\n",(ans+1)/2);}return 0;}

有向圖的連通性

強連通:如果兩個點:u,v是互相達到的

無向圖:聯通 有向圖:強連通

圖中有多少SCC:暴力O(V^2+E)

kosaraju算法O(V+E):反圖

(1)有向圖G,建立反圖rG,不會改變連通性

(2)對原圖G做DFS,標記點的先后順序,遞歸在最底層的點標記最小,回退過程中,其他點的優先級加大

(3)在反圖RG上做DFS,從優先級大的開始做

Tarjan算法O(V+E):用棧分離不同的SCC

最先入棧的點:是這個SCC的祖先,他的num[]=low[]

比上面要快些

#include<iostream>#include<cstring>#include<cmath>#include<algorithm>#include<cstdio>#include<queue>#include<map>#include<vector>#include<set>using namespace std;const int maxn=10010;const int INF=0x3fffffff;typedef long long LL;int cnt=0,dfn=0;int low[maxn],num[maxn];int sccno[maxn],stack[maxn],top;vector<int> g[maxn];void dfs(int u){stack[top++]=u;low[u]=num[u]=++dfn;for(int i=0;i<g[u].size();i++){int v=g[u][i];if(!num[v]){dfs(v);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++;while(1){int v=stack[top--];sccno[v]=cnt;if(u==v) break; //到達了祖先 }} } void tarjan(int n){ cnt=top=dfn=0; memset(sccno,0,sizeof(sccno)); memset(num,0,sizeof(num)); memset(low,0,sizeof(low)); for(int i=1;i<=n;i++){ if(!num[i]) dfs(i); } }  int main(){int n,m,u,v;while(scanf("%d %d",&n,&m),n!=0||m!=0){for(int i=0;i<=n;i++){g[i].clear();}for(int i=0;i<m;i++){scanf("%d %d",&u,&v);g[u].push_back(v);}tarjan(n);if(cnt==1) printf("Yes\n");else printf("No\n");} return 0;}