P3043 [USACO12JAN] Bovine Alliance G
并查集
每个连通块方案数独立。考虑一个连通块的情况,显然如果 \(m>n\) 一定无解,那么就只有 \(m=n\) 和 \(m=n-1\) 两种情况,前者是基环树,后者是树。
基环树的环上,第一条边选择的端点确定,其他也就确定,共有两种情况。环下的树选择固定。所有总方案数为 \(2\) 种。
树上所有边的端点选择完后,会剩下唯一的节点,将这个节点作为根,那么子树的选择也是固定的。由于这唯一的节点任意,所以方案数就是连通块的节点数。
那么就可以维护连通块内边数和点数计算答案了,用并查集即可。
复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back
using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m;
i64 ans = 1;
int fa[N], cnt[N], sz[N];
int find(int x) {
if(x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if(fx == fy) cnt[fy]++;
else {
fa[fx] = fy, cnt[fy] += cnt[fx] + 1;
sz[fy] += sz[fx];
}
}
int vis[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m;
for(int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
for(int i = 1; i <= m; i++) {
int u, v;
std::cin >> u >> v;
merge(u, v);
}
for(int i = 1; i <= n; i++) {
int x = find(i);
if(!vis[x]) {
if(cnt[x] > sz[x]) ans = 0;
else if(cnt[x] == sz[x]) ans = ans * 2 % mod;
else ans = ans * sz[x] % mod;
vis[x] = 1;
}
}
std::cout << ans << "\n";
return 0;
}
标签:std,sz,P3043,int,fy,USACO12JAN,fa,Alliance,ans
From: https://www.cnblogs.com/FireRaku/p/18290719