CF870E Points, Lines and Ready-made Titles 题解

经典套路横纵坐标连边，对位于 $(x,y)$ 坐标的点，从 $x$ 向 $y$ 连一条双向边，得到一张图。容易发现此时连通块之间互相独立，因此这里只考虑一个连通块的情况。

发现此时答案和连通块的具体形态无关，只和连通块内点和边的数量有关。因此设点的数量为 $v$ ，边的数量为 $e$ ：

若 $v=e+1$ 即形成一棵树，则此时在要画的图上总共有 $v$ 条边可选，每一条边均可选可不选，但是每个点最多选一条边，也就是说不能同时选择所有边。因此此时答案为 $2^v-1$ 。
若 $v\le e$ 则此时连通块中存在环，此时仍然总共有 $v$ 条边需要选，但是最多可以画 $e$ 条边（ $e\ge v$ ），因此不存在特殊情况，答案即为 $2^v$ 。

根据乘法原理将每个连通块的答案相乘，即得到最终的答案。用并查集维护，时间复杂度为 $O(n\log n)$ ，瓶颈在于对坐标离散化。

#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
const int N = 500010;
const int inf = 1e18;
const int mod = 1e9 + 7;

inline int power(int a, int b, int c)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % c;
        a = a * a % c, b >>= 1;
    }
    return ans;
}
inline int inversion(int x) { return power(x, mod - 2, mod); }

struct DSU
{
    int fa[N];
    inline DSU() { iota(fa, fa + N, 0); }
    inline void init(int maxn) { iota(fa, fa + maxn + 1, 0); }
    inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
    inline int merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x != y)
            return fa[x] = y, 1;
        return 0;
    }
} dsu;

int pwr[N], ecnt[N], vcnt[N];

signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    int n;
    cin >> n;
    map<int, int> m1, m2;
    int idx = 0;
    vector<pair<int, int>> e;
    for (int i = 1; i <= n; ++i)
    {
        int x, y;
        cin >> x >> y;
        if (!m1.count(x))
            m1[x] = ++idx;
        if (!m2.count(y))
            m2[y] = ++idx;
        e.emplace_back(m1[x], m2[y]);
        dsu.merge(m1[x], m2[y]);
    }
    pwr[0] = 1;
    for (int i = 1; i < N; ++i)
        pwr[i] = pwr[i - 1] * 2 % mod;
    int res = 1;
    for (auto &[x, y] : e)
        ++ecnt[dsu.find(x)];
    for (int i = 1; i <= idx; ++i)
        ++vcnt[dsu.find(i)];
    for (int i = 1; i <= idx; ++i)
        if (dsu.find(i) == i)
        {
            if (vcnt[i] > ecnt[i])
                res = res * (pwr[vcnt[i]] - 1 + mod) % mod;
            else
                res = res * (pwr[vcnt[i]]) % mod;
        }
    cout << res << '\n';
    return 0;
}

隐藏／恢复文章

随机文章