差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:lgwza:割点和桥 [2020/10/28 16:06]
lgwza 创建
+++ 2020-2021:teams:legal_string:lgwza:割点和桥 [2020/10/28 16:08] (当前版本)
lgwza
@@ 行 96: / 行 96: @@
         if(flag[i])
             printf("%d ",i);
+    return 0;
+}
+</code>
+</hidden>
+[[http://poj.org/problem?id=2117|POJ 2117 Electricity]]
+**题意**：选定一个结点，使得删掉它之后的连通块数量最多
+**题解**：对于根结点，删掉它之后新增连通块为其儿子数-1；对于非根结点的割点，删掉它之后新增的连通块等于其儿子数。
+代码：
+<hidden>
+<code cpp>
+#include<cstdio>
+#include<vector>
+#include<cstring>
+using namespace std;
+const int N=1e4+5;
+vector<int>adj[N];
+int n,m;
+int dfn[N],low[N],cnt;
+int block[N];
+void init(){
+    memset(block,0,sizeof(block));
+    memset(dfn,0,sizeof(dfn));
+    memset(low,0,sizeof(low));
+    for(int i=1;i<N;i++) adj[i].clear();
+    cnt=0;
+}
+void addedge(int u,int v){
+    adj[u].push_back(v);
+    adj[v].push_back(u);
+}
+void Tarjan(int u,int fa){
+    low[u]=dfn[u]=++cnt;
+    int child=0;
+    for(int i=0;i<adj[u].size();i++){
+        int v=adj[u][i];
+        if(v==fa) continue;
+        if(!dfn[v]){
+            child++;
+            Tarjan(v,u);
+            low[u]=min(low[u],low[v]);
+            if(fa!=u&&low[v]>=dfn[u]) block[u]++;
+        }
+        else low[u]=min(low[u],dfn[v]);
+    }
+    if(fa==u) block[u]=child-1;
+}
+int main(){
+    while(scanf("%d %d",&n,&m)&&(n||m)){
+        init();
+        for(int i=1;i<=m;i++){
+            int x,y;
+            scanf("%d %d",&x,&y);
+            x++;y++;
+            addedge(x,y);
+        }
+        int parts=0;
+        for(int i=1;i<=n;i++){
+            if(!dfn[i]){
+                parts++;
+                Tarjan(i,i);
+            }
+        }
+        int maxx=0;
+        for(int i=1;i<=n;i++) maxx=max(maxx,parts+block[i]);
+        printf("%d\n",maxx);
+    }
+    return 0;
+}
+</code>
+</hidden>
+===== 割边 =====
+和割点差不多，叫做桥。
+> 对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。严谨来说，就是：假设有连通图 $G=\{V,E\}$，$e$ 是其中一条边（即 $e\in E$），如果 $G-e$ 是不连通的，则边 $e$ 是图 $G$ 的一条割边（桥）。
+比如说，下图中，
+{{https://oi-wiki.org/graph/images/bridge4.png| 割边示例图}}
+红色箭头指向的就是割边。
+==== 实现 ====
+和割点差不多，只要改一处：$low_v>num_u$ 就可以了，而且不需要考虑根结点的问题。
+割边是和是不是根结点没关系的，原来我们求割点的时候是指点 $v$ 是不可能不经过父结点 $u$ 回到祖先结点（包括父结点），所以顶点 $u$ 是割点。如果 $low_v=num_u$ 表示还可以回到父结点，如果顶点 $v$ 不能回到祖先也没有另外一条回到父亲的路，那么 $u-v$ 这条边就是割边。
+==== 代码实现 ====
+下面代码实现了求割边，其中，当 ''%%isbridge[x]%%'' 为真时，''%%(father[x],x)%%'' 为一条割边。
+<hidden>
+<code cpp>
+int low[MAXN], dfn[MAXN], iscut[MAXN], dfs_clock;
+bool isbridge[MAXN];
+vector<int> G[MAXN];
+int cnt_bridge;
+int father[MAXN];
+void tarjan(int u, int fa) {
+  father[u] = fa;
+  low[u] = dfn[u] = ++dfs_clock;
+  for (int i = 0; i < G[u].size(); i++) {
+    int v = G[u][i];
+    if (!dfn[v]) {
+      tarjan(v, u);
+      low[u] = min(low[u], low[v]);
+      if (low[v] > dfn[u]) {
+        isbridge[v] = true;
+        ++cnt_bridge;
+      }
+    } else if (dfn[v] < dfn[u] && v != fa) {
+      low[u] = min(low[u], dfn[v]);
+    }
+  }
+}
+</code>
+</hidden>
+==== 例题 ====
+[[http://acm.hdu.edu.cn/showproblem.php?pid=4738|HDU4738 Caocao’s Bridges]]
+**题意**：输出一条边权最小的割边
+**题解**：模板题求割边，注意有重边和零边权等细节。
+代码：
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=1e3+5,INF=2e9;
+struct Edge{
+    int s,t,w;
+};
+vector<Edge>adj[N];
+bool ok;
+bool e[N][N];
+int times[N][N];
+int dfn[N],low[N],cnt,ans;
+void init(){
+    for(int i=1;i<N;i++) adj[i].clear();
+    memset(e,0,sizeof(e));
+    memset(times,0,sizeof(times));
+    memset(dfn,0,sizeof(dfn));
+    memset(low,0,sizeof(low));
+    cnt=ok=0;
+    ans=INF;
+}
+void addedge(int u,int v,int w){
+    adj[u].push_back((Edge){u,v,w});
+    adj[v].push_back((Edge){v,u,w});
+}
+void Tarjan(int u,int fa){
+    dfn[u]=low[u]=++cnt;
+    for(int i=0;i<adj[u].size();i++){
+        int v=adj[u][i].t;
+        int w=adj[u][i].w;
+        if(v==fa) continue;
+        if(!dfn[v]){
+            Tarjan(v,u);
+            low[u]=min(low[u],low[v]);
+            if(low[v]>dfn[u]){
+                if(!e[u][v]) ans=min(ans,w),ok=1;
+            }
+        }
+        else low[u]=min(low[u],dfn[v]);
+    }
+}
+int main(){
+    int n,m;
+    while(scanf("%d %d",&n,&m)&&(n||m)){
+        init();
+        for(int i=1;i<=m;i++){
+            int x,y,z;
+            scanf("%d %d %d",&x,&y,&z);
+            times[x][y]++;
+            times[y][x]++;
+            if(times[x][y]>1) e[x][y]=e[y][x]=1;
+            addedge(x,y,z);
+        }
+        int parts=0;
+        for(int i=1;i<=n;i++){
+            if(!dfn[i])
+                parts++,Tarjan(i,i);
+        }
+        if(parts>1) printf("0\n");
+        else{
+            if(ok) printf("%d\n",max(ans,1));
+            else printf("-1\n");
+        }
+    }
     return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具