Visits: 281

CF521E Cycling City

题面

• 给定一张 $n$ 个点 $m$ 条边的无向简单图。
• 问图中能否找到两个点，满足这两个点之间有至少三条完全不相交的简单路径。
• $n,m \le 2 \times 10^5$，图不保证连通。

题解

首先建出 dfs 树，那么有解的充要条件是存在至少一条树边被至少两条返祖边覆盖，这显然可以树上差分判定。

若有解，考虑如何构造方案。

可以通过两次二分，每次判定使用树上差分，找到两条至少有一条树边被它们覆盖的返祖边。

在只保留这两条边的情况下构造方案即可，具体方法见代码。

总时间复杂度 $\mathcal O(n \log m)$，可以做到线性但没必要。

代码

const int N = 2e5 + 7;
int n, m, v[N], dfn[N], num, f[N], t, d[N];
vi e[N], ans[3];
pi p[N];

void dfs(int x) {
    dfn[x] = ++num;
    for (auto y : e[x])
        if (!dfn[y]) f[y] = x, dfs(y);
        else if (y != f[x] && dfn[y] < dfn[x]) p[++t] = mp(x, y);
}

void dfs1(int x) {
    v[x] = 1;
    for (auto y : e[x])
        if (f[y] == x) dfs1(y), d[x] += d[y];
}

inline void work(int o) {
    --d[p[o].se], ++d[p[o].fi];
}

inline bool ask(int l, int r) {
    for (int i = l; i <= r; i++) work(i);
    for (int i = 1; i <= n; i++) if (!v[i]) dfs1(i);
    bool ok = 0;
    for (int i = 0; i <= n; i++) ok |= d[i] > 1, d[i] = v[i] = 0;
    return ok;
}

int main() {
    rd(n), rd(m);
    for (int i = 1, x, y; i <= m; i++)
        rd(x), rd(y), e[x].pb(y), e[y].pb(x);
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) dfs(i);
    if (!ask(1, t)) return prints("NO"), 0;
    else prints("YES");
    int l = 2, r = t;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (ask(1, mid)) r = mid;
        else l = mid + 1;
    }
    int R = l;
    l = 1, r = R - 1;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (ask(mid, R)) l = mid;
        else r = mid - 1;
    }
    int L = l;
    work(L), work(R);
    for (int i = 1; i <= n; i++) if (!v[i]) dfs1(i);
    int Y = 0;
    for (int i = 1; i <= n; i++)
        if (d[i] == 2 && dfn[i] > dfn[Y]) Y = i;
    int X = Y;
    ans[0].pb(X);
    while (d[X] == 2) ans[0].pb(X = f[X]);
    reverse(ans[0].begin(), ans[0].end());
    for (int i = 1; i < 3; i++) {
        int Z = X, o = i == 1 ? L : R;
        ans[i].pb(Z);
        while (Z != p[o].se) ans[i].pb(Z = f[Z]);
        ans[i].pb(Z = p[o].fi);
        while (Z != Y) ans[i].pb(Z = f[Z]);
    }
    for (int i = 0; i < 3; i++) {
        print(ans[i].size(), ' ');
        for (auto x : ans[i]) print(x, ' ');
        prints("");
    }
    return 0;
}