差别

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

--- 2020-2021:teams:legal_string:lgwza:割点和桥 [2020/10/28 16:07]
lgwza
+++ 2020-2021:teams:legal_string:lgwza:割点和桥 [2020/10/28 16:08] (当前版本)
lgwza
@@ 行 166: / 行 166: @@
         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;

CVBB ACM Team

用户工具

站点工具

差别

页面工具