新集合

[编程题]新集合

热度指数：146 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

集合 $s$ 中有整数 $1$ 到 $n$ ，牛牛想从中挑几个整数组成一个新的集合。

现在牛妹给牛牛加了 $m$ 个限制，每个限制包含两个整数 $u$ 和 $v$ ( $u\neq v$ )，且 $u$ 和 $v$ 不能同时出现在新集合中。

请问牛牛能组成的新集合多少种。

可以选 0 个数。

返回一个整数，即新集合的种类数。

示例1

输入

3,2,[(1,2),(2,3)]

输出

说明

当 n = 3 时，共有 8 个子集，当加上限制 (1, 2), (2, 3) 后，合法的自己有 [], [1], [2], [3], [1, 3] 共 5 个

备注:

第一个参数为 $n$ 。

第二个参数为 $m$ 。

第三个参数为 $m$ 对 (u, v) 。

$1 < n \leq 20 \quad 1\leq m \leq 400\quad 1 \leq u, v\leq n$

算法知识视频讲解

C++

勇敢牛牛，不怕困难！

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) {
    
    vector<int> nums(n);
    iota(begin(nums), end(nums), 1);
    
    vector<int> candidates;
    vector<vector<int>> subsets;
    function<void(int)> backtracking = [&](int p) {      
      subsets.emplace_back(candidates);
      for (int i = p; i < n; ++i) {
        candidates.emplace_back(nums[i]);
        backtracking(i + 1);
        candidates.pop_back();
      }
    };
    
    backtracking(0);
    
    int ans = 0;
    for (const auto& subset : subsets) {
      if (subset.size() < 2) { // 空集或只有一个元素的集合肯定满足条件
        ++ans;
        continue;
      }
      bool flag = true;
      for (const auto& l : limit) {
        if (find(begin(subset), end(subset), l.x) != end(subset) &&
            find(begin(subset), end(subset), l.y) != end(subset)) {
          flag = false; // 同时出现u, v
          break;
        }
      } 
      ans += flag;
    }
    
    return ans;
  }
};

发表于 2021-08-04 20:08:19 回复(0)

一只老风铃

因为题目互斥限制不多，采取朴素的枚举方法

即每个数字可能选或者不选，即0 =》2的n次方减一

若二进制位为1表示选取该数字，否则不选取

遍历limits 判断对应两个二进制位是否全部为1

 static bool judge(int num,int u,int v)
    {
        int val1=(num>>(u-1)&1);
        int val2=(num>>(v-1)&1);  //对应位上的数字
        if(val1==1 && val2==1)
            return false;
        else
            return true;  
    } 
    int solve(int n, int m, vector<Point>& limit) {
        // write code here
        int count=0;
        for(int val=0;val<=((1<<n)-1);val++)  //val为0=> 2的n次方-1
        {
            bool flag=true;
            for(auto item:limit)
            {
                if(judge(val,item.x, item.y)==false) //不满足互斥性
                {
                    flag=false;
                    break;
                }
            }
            if(flag)
                count++;
        }
        return count;
    }

发表于 2021-03-20 22:10:49 回复(0)