ABC334G Christmas Color Grid 2

第一次 AK abc，写篇题解记录一下。

原题传送门

分析

发现实际上是要求删去每个绿点之后会多出几个连通块。发现这跟割点的定义很像，于是考虑建图，在相邻的绿点之间连边。然后就只要知道每个点到底被包含在几个点双里。我们使用圆方树，此时就只需要统计每个点的度数就可以了。

代码

#include <iostream>
#define int long long
using namespace std;
const int P = 998244353;
char mp[1005][1005];
int n, m;
int f(int x, int y) { return (x - 1) * m + y; }
int head[1000005], nxt[10000005], to[10000005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
void adde(int x, int y) { add(x, y), add(y, x); }
int dfn[1000005], low[1000005], deg[2000005];
int ncnt;
int stk[1000005], sz;
void tarjan(int x) {
    stk[++sz] = x;
    dfn[x] = low[x] = ++ncnt;
    for (int i = head[x]; i; i = nxt[i]) {
        int v = to[i];
        if (!dfn[v]) {
            tarjan(v);
            low[x] = min(low[x], low[v]);
            if (low[v] == dfn[x]) {
                int t;
                do {
                    t = stk[sz--];
                    deg[t]++;
                } while (t != x);
                stk[++sz] = x;
            }
        } else 
            low[x] = min(low[x], dfn[v]);
    }
}
int qpow(int x, int y) {
    int ret = 1;
    while (y) {
        if (y & 1) 
            ret = ret * x % P;
        x = x * x % P;
        y >>= 1;
    }
    return ret;
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string str;
        cin >> str;
        for (int j = 1; j <= m; j++) {
            mp[i][j] = str[j - 1];
            if (mp[i][j] == '#') {
                if (mp[i - 1][j] == mp[i][j]) 
                    adde(f(i - 1, j), f(i, j));
                if (mp[i][j - 1] == mp[i][j]) 
                    adde(f(i, j - 1), f(i, j));
            }
        }
    }
    int xcnt = 0, cnt = 0, tot = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cnt += (mp[i][j] == '#');
            if (mp[i][j] == '#' && !dfn[f(i, j)]) 
                tarjan(f(i, j)), ++xcnt;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mp[i][j] == '#') {
                tot += xcnt - 1 + deg[f(i, j)];
                tot >= P ? (tot -= P) : 0;
            }
        }
    }
    cout << tot * qpow(cnt, P - 2) % P;
    return 0;
}