• 欢迎光临~

CF962F Simple Cycles Edges

开发技术 开发技术 2022-10-07 次浏览

CF962F Simple Cycles Edges - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

在一个无向图中,某个简单环等价于这个图中某个点数等于边数的点双连通分量。

为什么不是边双连通分量?

想象一个 8 字结构。这个 8 字整体并不是一个简单环(边数比点数多1),而是上下两个简单环中间共用一个点形成的。

从点双的角度来看,是上下两个点数等于边数的点双,这是正确的。

而从边双的角度来看,整个 8 字是一个边双,而上下两个环为这个 8 字边双的子图,并不是边双联通分量,等价性就破坏了。

可以这样理解:两个简单环可以共用一个点,而不能共用一条边。而边双是不能处理共用一个点的,所以边双不行。

在 tarjan 求解点双连通分量的过程中,同时用两个栈,分别存点和边。

然后判断到一个点双连通分量的时候,如果发现点数等于边数,那么存点的栈直接弹出,存边的栈边弹边把弹出的边记录在答案中,否则两个栈都直接弹就可以了。

但实际实现代码的时候发现,点数和边数似乎本来就需要弹栈同时统计?不会还用到一个数组来存弹出来的边,然后再回去给数组标记吧。这样就麻烦了。

我们发现存点的栈无论如何都是直接弹,那么点数直接边弹边统计即可。

而边数,其实就是栈中 ((u, v)) 这条边,一直往上到栈顶的这些边的数量。那么一开始弹入 ((u, v)) 之前我们记录一下存边栈的大小 (erz),之后检测到点双,弹栈之前栈的大小 (s) 减去 (erz) 就是边的数量。具体看代码。

(mathcal{O}(n + m))

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2022-10-07 22:53:38 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2022-10-08 00:45:49
 */
#include <bits/stdc++.h>
inline int read() {
    int x = 0;
    bool flag = true;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            flag = false;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    if(flag)
        return x;
    return ~(x - 1);
}

const int maxn = (int)1e5 + 5;
const int maxm = (int)1e5 + 5;
typedef std :: pair <int, int> pii;

std :: vector <pii> G[maxn];
std :: vector <int> ans;
std :: stack <int> vst, est;

int dfn[maxn], low[maxn], times;

inline bool gmi(int &a, int b) {
    return b < a ? a = b, true : false;
}

void tarjan(int u, int lst) {
    dfn[u] = low[u] = ++times;
    vst.push(u);

    for (pii e : G[u]) {
        int v = e.first, id = e.second;
        if (!dfn[v]) {
            int erz = est.size();
            est.push(id);
            tarjan(v, id);
            gmi(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                int ent = est.size() - erz, vnt = 1;
                while (!vst.empty()) {
                    int x = vst.top();
                    vst.pop();
                    ++vnt;
                    if (x == v)
                        break;
                }

                // printf("%d %d %dn", low[u], low[v], ent);
                while (!est.empty()) {
                    int x = est.top();
                    est.pop();
                    if (ent == vnt)
                        ans.push_back(x);
                    if (x == id)
                        break;
                }
            }
        } else if (id != lst) {
            // 我们刚刚是从哪条边来的,不能从这条边上返回去
            // 事实上还有一种写法是 tarjan 在传参 u 的同时也传参 u 的父亲 fa,然后检测 v != fa 防止回去
            // 这种写法在无重边,或者求点双/割点的时候都没有问题(你把一个点删了重边一起没,不影响)
            // 但是在有重边环境下,求边双/桥的时候就会出问题了,比如 1 - 2 之间两条边,删除一条可以走另一条。这种情况下只能像我这么写
            // 具体可以看洛谷中边双的板题 P8436
            gmi(low[u], dfn[v]);
            est.push(id);
        }
    }
}

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        G[u].emplace_back(v, i);
        G[v].emplace_back(u, i);
    }

    for (int u = 1; u <= n; ++u)
        if (!dfn[u])
            tarjan(u, 0);
    
    printf("%dn", (int)ans.size());
    std :: sort(ans.begin(), ans.end());
    
    for (auto x : ans)
        printf("%d ", x);
    puts("");
    return 0;
}
程序员灯塔
转载请注明原文链接:CF962F Simple Cycles Edges
喜欢 (0)