CCPC长春G题 (xjb搜索)

n <=50的图,计算这样的子点集个数,点集中存在点数 >= 3并且是团或者是独立集的子集。

反着算,计算不存在团和独立集的点集个数,有一个可以想到的结论点集尺寸>=6时一定会出现团和独立集,于是最多跑5层的dfs,xjb搜索一下好像是可以过的。。

 

LEAVE A COMMENT