题解 | #新集合#

题意

在1-n中选出任意个数(可以是0个数)组成新的集合，但要满足m个限制条件。每个条件(u,v)限制u,v两个数不能同时在新的集合中。

解法

我们观察到 ，而每个数有选与不选两种状态，所以总状态数为。 对于我们来说是一个可以接受的状态数，也就是说在的数据范围内，的复杂度是可以接受的，我们可以暴力搜索完成这道题。
那么剩下来的就很简单的。我们只需要依次从1到n枚举每个数是否可以选中(与题目给出的限制条件对比)，如果可以选中，答案就加上选中后的数目。最后答案再加上不选当前这个数的结果。
我们可以使用long long二进制状态压缩储存状态。(因为long long类型的大小很小，可以很方便的在调用的时候传递。当然也可以使用全局数组，只要记得还原就行)
(在每次插入前判断是否矛盾)

/**
 * struct Point {
 *    int x;
 *    int y;
 *    Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 集合大小
     * @param m int 限制数量
     * @param limit Pointvector 不能同时出现的(u,v)集合
     * @return int
     */
    int solve(int n, int m, vector<Point>& limit) {
        // 判断能不能选 
        return dfs(n,1,0,limit);
    }
    int dfs (int n,int num,long long state,vector<Point>& limit) {
        if (num == n + 1) return 1;
        bool can = true;
        for (auto &p:limit) {
            if(p.x == num) {
                if ((state >> p.y) & 1) {
                    can = false;
                    break;
                }
            }
            if(p.y == num) {
                if ((state >> p.x) & 1) {
                    can = false;
                    break;
                }
            }
        }
        int ret = 0;
        if (can) {
            ret += dfs (n,num + 1,state | (1 << num),limit);
        }
        ret += dfs (n,num + 1,state,limit);
        return ret;
    }
};