广义串并联图 / 缩边
以下只讨论无向图。
- K4：\(4\) 个点 \(6\) 条边的完全图；
- 同胚：删去所有二度点（删去该点，并用一条边连接该点连接的两个点）后，两图同构；
对于一个图 \(G(V,E)\)，若其不存在与 K4 同胚的子图，则称其为广义串并联图。
对于一个广义串并联图，可以通过以下三种操作将其缩为一个点：
- 删 \(1\) 度点：度数为 \(1\) 的点可以直接删去，不会影响图的其它部分；
- 删 \(2\) 度点：删去该点，并用一条边连接该点连接的两个点；
- 叠合重边：将两条重边叠合为 \(1\) 条；
在某些题目中，我们可以运用这一方法，将问题分解为 \(3\) 个子问题：
- 处理 \(1\) 度点 所连接的唯一一条边产生的贡献；
- 求出两条边串联起来的等效边；
- 求出两条边并联起来的等效边；
如果原图是广义串并联图，则直接缩边即可得到答案。其余情况，如果题目保证 \(m\le n+k\)（其中 \(k\) 很小），则直接缩边后剩下的图一定满足 \(n'\le 2k,\ m'\le 3k\)。
证明考虑三类缩边操作：
- 删 \(1\) 度点：
--m, --n；
- 删 \(2\) 度点：
--m, --n；
- 叠合重边：
--m；
因此最终的图一定有 \(m'\le n'+k\)；同时最终的图上一定不包含度数小于 \(3\) 的节点（都被删掉了），因此有 \(3n\le 2m\)，联立解得 \(n\le 2k,m\le 3k\)。对于 \(k\) 较小的情况可以直接暴力搜索求解。
技巧
若题目给定的图满足 \(m\le n+k\)，其中 \(k\) 很小，可以考虑使用广义串并联缩边之后暴力解决。
代码容易出现的错误
- 度数数组
deg[u] 和邻接表的大小 edg[u].size() 一定要时刻保持匹配。
- 一个点（\(1\) 度点、\(2\) 度点）被删掉后，一定要将其
deg 标记为 \(0\)，保证不会被删除第 \(2\) 次。
例题
250218 模拟赛 T2 color
题意
给定一个 \(n\) 个点 \(m\) 条边的联通无向图，给图上每个点染上 \(k\) 种颜色中的一种，且要
求每一条边的两个端点不同色（不需要使用全部 \(k\) 种颜色），求方案数 \(\bmod 10^9+7\)。
\(n\le 10^5, m\le n+5\)
按照题解的说法，图的染色问题在多项式时间内不可解。注意到题目给定了一额外限制条件：\(m\le n+5\)。对于这种形式的约束条件，我们可以用广义串并联图的缩边方法，缩掉 \(1\) 度点和 \(2\) 度点，并叠合重边，最终会形成一个 \(n'\le 10,\ m'\le 15\) 的图，可以直接暴力求解。
虽然题目要求一条边的两个端点不同色；但缩边的过程中，两条边串联形成的等效边，两端点可以同色。
因此我们还需要考虑到这种情况。具体的，我们给每条边赋予两个权值：\(w_1,w_2\)，分别表示两端点颜色相等、不等，等效边内部点染色的方案数（容易注意到边内部染色方案和两端点具体的颜色无关，只与其相等关系有关）。
考虑三类缩边操作：
- 缩 \(2\) 度点时考察中间点和两端点的颜色关系，即可得出转移；
- 缩 \(1\) 度点时直接将连边的 \(w_1+w_2\) 乘到答案的系数上；
- 叠合重边时直接将 \(w_1,w_2\) 对应相乘即可。
最终我们会得到一个 \(n'\le 10\) 的图，在上面暴力搜索每种本质不同的方案，统计其出现次数（\(\binom{k}{c}c!\)）和等效边内部的贡献即可。
代码
| #include<iostream>
#include<set>
#include<queue>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
struct Edge {
int v, w1, w2;
inline bool operator<(const Edge &other) const {
return v < other.v;
}
};
struct Pt {
int u, deg;
inline bool operator>(const Pt &other) const {
return deg > other.deg;
}
};
int n, m, k;
int deg[N], vis[N];
set<Edge> E[N];
priority_queue<Pt, vector<Pt>, greater<Pt> > V;
int ans, mul = 1;
int valid[12], n2;
int col[N];
// 暴力染色，每个点只处理 u <-> v 且 v < u 的点 v，可以保证每条边只被处理一次
void dfs(int x, int ccnt, int pans) {
if(!pans) return;
if(x == n2 + 1) {
for(int i = k; i >= k - ccnt + 1; i--) {
pans = pans * i % MOD;
}
ans = (ans + pans) % MOD;
return;
}
for(int i = 1; i <= ccnt + 1; i++) {
int tmp = 1;
for(auto j = E[valid[x]].begin(); j != E[valid[x]].end(); ++j) {
if(j->v > valid[x]) break;
tmp = (tmp * ((i == col[j->v]) ? j->w1 : j->w2)) % MOD;
}
col[valid[x]] = i;
dfs(x + 1, max(i, ccnt), pans * tmp % MOD);
}
}
// 加边的同时去除重边
void addEdge(int u, int v, int w1, int w2) {
auto it = E[u].find({v, 0, 0});
if(it != E[u].end()) {
int ww1 = it->w1, ww2 = it->w2;
E[u].erase({v, 0, 0});
E[v].erase({u, 0, 0});
E[u].insert({v, w1 * ww1 % MOD, w2 * ww2 % MOD});
E[v].insert({u, w1 * ww1 % MOD, w2 * ww2 % MOD});
--deg[u], --deg[v];
V.push({u, deg[u]});
V.push({v, deg[v]});
} else {
E[u].insert({v, w1, w2});
E[v].insert({u, w1, w2});
}
}
signed main() {
// freopen("color.in", "r", stdin);
// freopen("color.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
E[u].insert({v, 0, 1});
E[v].insert({u, 0, 1});
}
for(int i = 1; i <= n; i++) {
deg[i] = E[i].size();
V.push({i, deg[i]});
}
while(!V.empty() && V.top().deg <= 2) {
int u = V.top().u;
if(vis[u] || V.top().deg != deg[u]) {
V.pop();
continue;
}
V.pop();
if(deg[u] == 0) {
// 如果原图是广义串并联，则可以缩为一个点
mul = mul * k % MOD;
} else if(deg[u] == 1) {
// 缩一度点
Edge e = *E[u].begin();
mul = mul * (e.w1 + e.w2 * (k - 1) % MOD) % MOD;
--deg[e.v];
E[e.v].erase({u, 0, 0});
V.push({e.v, deg[e.v]});
} else {
// 缩二度点
Edge e1 = *E[u].begin();
Edge e2 = *E[u].rbegin();
int w1 = (e1.w1 * e2.w1 % MOD + e1.w2 * e2.w2 % MOD * (k - 1) % MOD) % MOD;
int w2 = (e1.w1 * e2.w2 % MOD + e1.w2 * e2.w1 % MOD + e1.w2 * e2.w2 % MOD * (k - 2) % MOD) % MOD;
E[e1.v].erase({u, 0, 0});
E[e2.v].erase({u, 0, 0});
// 叠合重边在 addEdge 中处理
addEdge(e1.v, e2.v, w1, w2);
}
deg[u] = 0;
}
for(int i = 1; i <= n; i++) {
if(deg[i] >= 3) valid[++n2] = i;
}
// 此时保证 n2 <= 10
dfs(1, 0, 1);
cout << ans * mul % MOD << endl;
return 0;
}
|
题意
给定一个图，保证该图由一个仙人掌添加一条边形成；问其生成树数量对 \(998244353\) 取模的结果。
\(n,m\le 2\times 10^5\)；
注意到仙人掌添加一条边后，仍然是广义串并联图，可以缩为一个点。
考虑如何设置边的状态。生成树要求连通并且不能有环。一条等效边内部的节点只能通过等效边的两个端点连接到外部，因此每一个内部节点都至少连接到一个端点。
考虑串联：分讨中间点连接到哪个端点，并且是否同时连接。这需要我们记录每条等效边两端点 \(u,v\) 连通和不连通的方案数，分别记为 \(cc\) 和 \(cd\)。注意到并联和叠合重边时这两个属性也是容易转移的。直接做即可。
代码
| #include<iostream>
#include<set>
#include<queue>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
const ll MOD = 998244353;
struct Edge {
int v;
ll cc, cd;
inline bool operator<(const Edge &b) const {
return v < b.v;
}
};
struct Node {
int u, deg;
inline bool operator<(const Node &b) const {
return deg > b.deg;
}
};
int n, m;
ll ans = 1;
int deg[N];
set<Edge> edg[N];
priority_queue<Node> mn;
void addEdge(int u, int v, ll cc, ll cd) {
auto it = edg[u].find({v});
if(it != edg[u].end()) {
ll nc = (cc * it->cd + cd * it->cc) % MOD;
ll nd = cd * it->cd % MOD;
edg[u].erase({v});
edg[v].erase({u});
edg[u].insert({v, nc, nd});
edg[v].insert({u, nc, nd});
--deg[u], --deg[v];
mn.push({u, deg[u]});
mn.push({v, deg[v]});
} else {
edg[u].insert({v, cc, cd});
edg[v].insert({u, cc, cd});
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
addEdge(u, v, 1, 1);
++deg[u];
++deg[v];
}
for(int i = 1; i <= n; i++) mn.push({i, deg[i]});
while(!mn.empty()) {
int u = mn.top().u;
if(mn.top().deg != deg[u]) {
mn.pop();
continue;
}
mn.pop();
if(deg[u] == 0) continue;
else if(deg[u] == 1) {
ans = ans * edg[u].begin()->cc % MOD;
int v = edg[u].begin()->v;
--deg[v];
edg[v].erase({u});
mn.push({v, deg[v]});
} else if(deg[u] == 2) {
Edge e1 = *edg[u].begin();
Edge e2 = *edg[u].rbegin();
edg[e1.v].erase({u});
edg[e2.v].erase({u});
addEdge(e1.v, e2.v, e1.cc * e2.cc % MOD, (e1.cc * e2.cd + e1.cd * e2.cc) % MOD);
}
deg[u] = 0;
}
cout << ans << endl;
return 0;
}
|