用二分图求最大独立集

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
const int maxn = 5005;
unordered_map<int, int> mp;
vector<int> v, c, z;
vector<int> vec[maxn];
int data[maxn], index[maxn];
int pre[maxn], vis[maxn];
bool used[maxn];
int n, cnt, ans;
void dfs(int u, int fa, int t){
    used[u] = true;
    if(t == 1)    v.push_back(u);
    else    z.push_back(u);
    for(int i = 0; i < vec[u].size(); i++){
        int v = vec[u][i];
        if(v == fa || used[v])    continue;
        dfs(v, u, t^1);
    }
}
bool found(int u, int t){
    vis[u] = t;
    for(int i = 0; i < vec[u].size(); i++){
        int v = vec[u][i];
        if(vis[v] == t)    continue;
        vis[v] = t;
        if(pre[v] == 0 || found(pre[v], t)){
            pre[v] = u;
            pre[u] = v;
            return true;
        }
    }
    return false;
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        scanf("%d", &data[i]);
        mp[data[i]] = ++cnt, index[cnt] = data[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            int now = (data[i] ^ data[j]);
            if((now & (now-1)) == 0){
                vec[mp[data[i]]].push_back(mp[data[j]]);
                vec[mp[data[j]]].push_back(mp[data[i]]);
            }
        }
    }
    for(int i = 1; i <= cnt; i++){
        if(!used[i])    dfs(i, 0, 1);
    }
    for(int i = 0; i < v.size(); i++){
        if(found(v[i], i+1))    ans++;
    }
    printf("%d\n", cnt-ans);
    for(int i = 1; i <= cnt; i++)    vis[i] = 0;
    for(int i = 0; i < v.size(); i++){
        if(!pre[v[i]])    found(v[i], 1);
    }
    for(int i = 0; i < v.size(); i++){
        if(vis[v[i]])    printf("%d ", index[v[i]]);//左边标记的
    }
    for(int i = 0; i < z.size(); i++){
        if(!vis[z[i]])    printf("%d ", index[z[i]]);//右边未标记的
    }
}