焦点速讯：AcWing395. 冗余路径

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

焦点速讯：AcWing395. 冗余路径

2023-01-07 23:06:54 来源：博客园

(资料图)

题目大意

$\qquad$给定一张无向图，求至少增加多少条边才能将这张图变成一个e-dcc边双连通分量。

解题思路

$\qquad$从边双的性质入手：$$边双连通分量内部的两个点之间至少有两条不重合的路径$$$\qquad$这刚好符合题目对草地的描述，所以可以推出这题是以上大意。

$\qquad$我们将原图进行缩点，可以得到一个新图，这样的新图可以化成一个树的形式：

o  / \ o   o/ \ / \       o   o o o

然后对于每个叶子节点，想增加一些边让整个图变成一个双连通分量的话，我们就应该让每个节点都处于一个简单环，这样图中才会不存在桥，这是因为每个点都在环上，而环有一个性质：任意一条边断开环上的点仍然是互相连通的，所以我们可以得出一个策略：叶子节点两两分组连线，这样会出现两种情况：

\[1.同一组的两片叶子有同一个父节点，那么这两片叶子和他们的父节点可以构成环\]\[2.同一组的两片叶子有不同的父节点，那么这两片叶子和他们的父节点以及LCA可以构成环\]

所以我们选择两片叶子分组，可以分成的组数有两种情况：

\[1.当叶子有奇数片的时候，需要\left \lfloor \frac{cnt}{2} \right \rfloor +1条线\]\[2.当叶子有偶数片的时候，需要\frac{cnt}{2}\]\[综上所述，需要\left \lceil \frac{cnt}{2} \right \rceil 条线\]

所以答案就$OK$了，这里的叶子节点就是缩点之后度数为$1$的点。

代码

#include #include #include #include using namespace std;const int N = 2e5 + 10;int h[N], e[N], ne[N], w[N], idx;int dfn[N], low[N], stk[N], top;int stmp, dcc_cnt, d[N], id[N];int n, m, is_bridge[N], cnt;void add(int a, int b) {    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}void tarjan(int u, int edg) {    low[u] = dfn[u] = ++ stmp;    stk[ ++ top] = u;        for (int i = h[u]; ~i; i = ne[i])     {        int j = e[i];        if (!dfn[j])         {            tarjan(j, i);            low[u] = min(low[u], low[j]);            if (dfn[u] < low[j])                 is_bridge[i] = is_bridge[i ^ 1] = true ;        }        else if (i != (edg ^ 1))             low[u] = min(low[u], dfn[j]);    }        if (low[u] == dfn[u])     {        ++ dcc_cnt; int y;        do         {            y = stk[top -- ];            id[y] = dcc_cnt;        } while (y != u);    }}int main() {    scanf("%d%d", &n, &m);        memset(h, -1, sizeof h);    while (m -- )     {        int u, v;        scanf("%d%d", &u, &v);        add(u, v), add(v, u);    }        tarjan(1, -1);        for (int i = 0; i < idx; i ++ )             if (is_bridge[i]) d[id[e[i]]] ++ ;            for (int i = 1; i <= dcc_cnt; i ++ )         if (d[i] == 1) cnt ++ ;        printf("%d\n", cnt + 1 >> 1);        return 0;}

关键词：互相连通这是因为两种情况