Tokitsukaze and Synthesis and Traits

原题链接

TAG：建有向图，思维

思路

题意转化：在一张可能不连通的无向图中，进行 \(q\) 次查询，每次给出 \(k\) 个点，查询 \(\frac{k\cdot(k-1)}{2}\) 个边，有多少边在原图中出现过。

考虑给原图的边定向。设 \(d_x\) 表示节点 \(x\) 的度，则对于原图中的一条边 \((u, v)\),若 \(d_u<d_v\)，则连接 \(u→v\)，否则连接 \(v→u\)。给原图的边定向后，每个点的出边 \(≤\sqrt{m}\)。对于每次查询，用桶记录每个点，然后直接遍历每个查询的点的所有出边即可，常数较小。总时间复杂度为 \(O(\sqrt{m}·\sum k)\)。

证明:对于一个查询的点 \(x\)，设 \(cnt_x\) 表示 \(x\) 的出边数量。若 \(cnt_x<\sqrt{m}\)，则显然遍历所有出边的时间复杂度小于 \(O(\sqrt{m})\)；若 \(cnt>\sqrt{m}\)，由于 \(x→y (d_x<d_y)\)，则总边数最多为\(cnt_x·d_y=m\)，所以 \(cnt_x\) 不超过 \(\sqrt{m}\)。

时间复杂度 \(O(m\sqrt{m})\)

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m, q;
    cin >> n >> m >> q;

    // 记录度数
    vector<pair<int, int>> merge(m);
    vector<int> deg(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        deg[u]++;
        deg[v]++;
        merge[i] = {u, v};
    }

    // 建有向图
    vector<vector<int>> h(n);
    for (auto [u, v] : merge) {
        if (deg[u] < deg[v]) h[u].push_back(v);
        else h[v].push_back(u);
    }

    // 处理询问
    while (q--) {
        int k;
        cin >> k;
        vector<int> ver(k); // 询问点集
        vector<bool> st(n, false); // 点是否在点集中
        for (int &x : ver) {
            cin >> x;
            x--;
            st[x] = true;
        }

        // 枚举出边
        int res = 0;
        for (auto x : ver) {
            for (auto to : h[x]) {
                res += st[to];
            }
        }
        cout << res << "\n";
    }

    return 0;
}