新集合

[编程题]新集合

热度指数：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$

算法知识视频讲解

elkkkk

发表于 2021-09-07 09:40:32

题意：给你一个的整数集合，再给你个限制条件，条件的形式如下：第个条件给你两个数，表示和不能在同一个集合中现在问你总共有多少种选法，使得所选集合满足条件？解法一（暴力枚举）发现本题中数据范围，于是我们可以直接枚举每一个数字选或者不选两展开全文

xqxls

发表于 2021-09-03 21:07:02

题意整理给定一个集合包含1到n共n个数，从中选若干数出来组成新的集合。规定一个限制数组，限制数组里的每一个数对不能同时出现在新集合中。求这样的新集合有多少个。方法一（二进制枚举） 1.解题思路定义1个mask，表示1到n有没有出现过，若mask最低位为1，则表示1出现过，次低位为1，展开全文

哆啦B梦2112

发表于 2021-09-03 15:32:32

题意在1-n中选出任意个数(可以是0个数)组成新的集合，但要满足m个限制条件。每个条件(u,v)限制u,v两个数不能同时在新的集合中。解法我们观察到，而每个数有选与不选两种状态，所以总状态数为。对于我们来说是一个可以接受的状态数，也就是说在的数据范围内，的复杂度是可以接受的，我们可以暴力展开全文

leaves0924

发表于 2021-09-10 22:48:24

题目描述集合 s 中有整数 1 到 n，牛牛想从中挑几个整数组成一个新的集合。现在牛妹给牛牛加了 m 个限制，每个限制包含两个整数 u 和 v ，且 u 和 v 不能同时出现在新集合中。请问牛牛能组成的新集合多少种。可以选 0 个数。返回一个整数，即新集合的种类数。示例1输入：3,2,[(1, 展开全文