链接：https://ac.nowcoder.com/acm/contest/23156/1023
来源：牛客网

题目描述

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

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

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

可以选 0 个数。

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

示例1

输入

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

返回值

复制  
5

说明 

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

备注: 

		

			第一个参数为 n。
		


		

			第二个参数为 m 。
		


		

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


		

			1<n≤20 1≤m≤400
思路：
1.dfs,每一层有两种选择：选或者不选，然后递归下一层，边界是dep>n。此时对这个集合进行检查，对于每一根limit对，if(use[u]&&use[v])，cnt就不加1。
2.this->n=n,this->m=m,this->limit=limit;注意核心代码的写法。 
/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */

class Solution {
public:
    vector<Point> limit;
    int n,m,cnt=0;
    int use[22];
    void dfs(int k){
        if(k>n){
            for(int i=0;i<m;i++){
                int u=limit[i].x,v=limit[i].y;
                if(use[u]&&use[v])return;
            }
            cnt++;
            return ;
        }
        use[k]=0;dfs(k+1);
        use[k]=1;dfs(k+1);
        
    }
    int solve(int n, int m, vector<Point>& limit) {
        this->n=n,this->m=m,this->limit=limit;
        memset(use,0,sizeof(use));
        dfs(1);
        return cnt;
        
    }
};