题解 | 有向二分图构造

C++ 随机数构造

#include <iostream>
#include <random>
#include <vector>
using namespace std;

struct Edge {
    int u, v, id;
};

int main() {
    int t, n, m;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        // 给每个点随机染色 遍历所有边
        // 若核心边数 >= M/4 则输出 否则重新染色
        vector<Edge> edges(m);
        for (int i=0; i<m; i++) {
            cin >> edges[i].u >> edges[i].v;
            edges[i].id = i+1;
        }
        // 随机生成n个0或1 
        random_device rd;
        mt19937 rng(rd());
        uniform_int_distribution<int> dist(0,1);
        vector<int> color(n+1); // 从编号1开始
        for (int i=0; i<10; i++) {  // 最多随机10次 - 一定存在至少一个可能的解
            for (int u=1; u<=n; u++) {
                color[u] = dist(rng);
            }
            vector<int> ans;
            for (auto& e : edges) {
                if (color[e.u]==0 && color[e.v]==1) {
                    ans.push_back(e.id);
                }
            }
            // cout << ans.size() << endl;
            if (ans.size()>=m/4+1) {
                cout << ans.size() << endl;
                for (auto id : ans) {
                    cout << id << ' ';
                }
                cout << endl;
                break;
            }
        }
    }
}
// 64 位输出请用 printf("%lld")