连通性

无向图的联通分量

割点:在一个联通分量里面有一些关键点,如果删除它,会把这个联通分量分为更多。 割边——双连通问题

有多少个割点: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;}