Visits: 325

CF639F Bear and Chemistry

题意

• 给定一张 $n$ 个点 $m$ 条边的初始无向图。
• $q$ 次询问，每次询问给定一个点集 $V$ 和边集 $E$。
• 你需要判断，将 $E$ 中的边加入初始无向图之后，$V$ 中任意两个点 $x,y$ 是否都能在每条边至多经过一次的情况下从 $x$ 到 $y$ 再回到 $x$。
• $n,m,q,\sum |V|, \sum |E| \le 3 \times 10^5$，强制在线。

题解

两个点能来回走一次等价于这两个点在同一个边双连通分量中，因此对于单组询问，我们只需要跑一次 tarjan 就行了。

多组询问的情况下，注意到点数和边数的总数并不大，因此考虑先将初始无向图缩点成一个森林，然后对于每次询问建出虚树，再连边跑 tarjan。

设 $n,m,q,\sum |V|, \sum |E|$ 都同阶，时间复杂度为 $\mathcal O(n \log n)$。

代码

const int N = 3e5 + 7, M = 6e5 + 7;
int q, rt[N], f[N][21], d[N], dfn[N], tot, s[N], t;

struct Undirected_Gragh_edcc {
    int n, m, h[N], e[M*2], t[M*2], tot = 1, dfn[N], low[N], num;
    bool b[M*2];
    int c[N], dcc;
    vi bridge, ec[N];
    inline void add(int x, int y, int o = 1) {
        e[++tot] = y, t[tot] = h[x], h[x] = tot;
        if (o) add(y, x, 0);
    }
    void tarjan(int x, int f) {
        dfn[x] = low[x] = ++num;
        for (int i = h[x]; i; i = t[i])
            if (i ^ f ^ 1) {
                int y = e[i];
                if (!dfn[y]) {
                    tarjan(y, i), low[x] = min(low[x], low[y]);
                    if (low[y] > dfn[x]) b[i] = b[i^1] = 1, bridge.pb(i);
                } else low[x] = min(low[x], dfn[y]);
            }
    }
    void dfs(int x) {
        c[x] = dcc;
        for (int i = h[x]; i; i = t[i]) {
            int y = e[i];
            if (c[y] || b[i]) continue;
            dfs(y);
        }
    }
    inline void Bridge() {
        for (int i = 1; i <= n; i++)
            if (!dfn[i]) tarjan(i, 0);
    }
    inline void edcc() {
        Bridge();
        for (int i = 1; i <= n; i++)
            if (!c[i]) ++dcc, dfs(i);
    }
    inline void Brighe(vi p) {
        for (int x : p)
            if (!dfn[x]) tarjan(x, 0);
    }
    inline void edcc(vi p) {
        Brighe(p);
        for (int x : p)
            if (!c[x]) ++dcc, dfs(x);
    }
    inline void main() {
        edcc();
        for (int i = 2; i <= tot; i++)
            if (b[i]) ec[c[e[i]]].pb(c[e[i^1]]);
    }
    inline void init(vi p) {
        tot = 1, num = dcc = 0;
        for (int x : p) h[x] = dfn[x] = low[x] = c[x] = 0;
        for (int i : bridge) b[i] = b[i^1] = 0;
        bridge.clear();
    }
} gragh, g;

void dfs(int x) {
    dfn[x] = ++tot;
    for (int y : gragh.ec[x]) 
        if (y != f[x][0]) {
            d[y] = d[x] + 1, f[y][0] = x, rt[y] = rt[x];
            for (int i = 1; f[y][i-1]; i++)
                f[y][i] = f[f[y][i-1]][i-1];
            dfs(y);
        }
}

inline int lca(int x, int y) {
    if (d[x] > d[y]) swap(x, y);
    for (int i = 20; ~i; i--)
        if (d[f[y][i]] >= d[x]) y = f[y][i];
    if (x == y) return x;
    for (int i = 20; ~i; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

inline void virtual_tree(vi &p) {
    sort(p.begin(), p.end(), [](int x, int y) { return dfn[x] < dfn[y]; });
    int o = 0;
    vi q = p;
    for (int x : p) {
        if (t && rt[x] != o)
            while (--t) g.add(s[t+1], s[t]);
        int lca = ::lca(x, s[t]);
        if (lca != s[t]) {
            while (t && d[s[t-1]] >= d[lca]) g.add(s[t], s[t-1]), --t;
            if (s[t] != lca) g.add(s[t], lca), s[t] = lca, q.pb(lca);
        }
        s[++t] = x, o = rt[x];
    }
    if (t) while (--t) g.add(s[t+1], s[t]);
    p = q;
}

inline void work(int &x, int R) {
    x = x + R > gragh.n ? x + R - gragh.n : x + R; 
}

int main() {
    rd(gragh.n), rd(gragh.m), rd(q);
    for (int i = 1, x, y; i <= gragh.m; i++)
        rd(x), rd(y), gragh.add(x, y);
    gragh.main();
    for (int i = 1; i <= gragh.dcc; i++)
        if (!rt[i]) rt[i] = i, d[i] = 1, dfs(i);
    for (int i = 1, n, m, R = 0; i <= q; i++) {
        rd(n), rd(m);
        vi v, p;
        vector<pi> e;
        for (int i = 1, x; i <= n; i++)
            rd(x), work(x, R), v.pb(x = gragh.c[x]), p.pb(x);
        for (int i = 1, x, y; i <= m; i++) {
            rd(x), rd(y), work(x, R), work(y, R);
            x = gragh.c[x], y = gragh.c[y];
            if (x == y) continue;
            e.pb(mp(x, y)), p.pb(x), p.pb(y);
        }
        sort(p.begin(), p.end());
        p.erase(unique(p.begin(), p.end()), p.end());
        virtual_tree(p);
        for (pi o : e) g.add(o.fi, o.se);
        g.edcc(p);
        int k = g.c[v[0]];
        bool ok = 1;
        for (int x : v) if (g.c[x] != k) ok = 0;
        prints(ok ? "YES" : "NO");
        if (ok) R = (R + i) % gragh.n;
        g.init(p);
    }
    return 0;
}