#P12371. 【模板】最大团/最大独立集

    ID: 13994 远端评测题 3000ms 1024MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>搜索Special Judge深度优先搜索 DFS剪枝折半搜索 meet in the middle

【模板】最大团/最大独立集

题目描述

给定一个无向图 GG,你需要对其分别求出:

  • GG 的一组最大团。
  • GG 的最大团个数。
  • GG 的一组最大独立集。
  • GG 的最大独立集个数。

GG 的最大团为 GG 的最大完全子图,完全图为各点间两两均有连边的图。

GG 的最大独立集为 GG 的最大零子图,零图为各点间两两均没有边的图。

输入格式

第一行两个正整数 nnmm,分别表示图 GG 的节点个数以及无向边条数。

接下来 mm 行,每行两个数 u,vu,v 表示一条无向边连接的两个节点。

图可能会有重边,不会有自环。

输出格式

第一行两个整数 a,ba,b,分别表示图 GG 的最大团大小(即最大团的节点个数)以及最大团个数。

第二行 aa 个整数,表示最大团的点集。

第三行两个整数 p,qp,q,分别表示图 GG 的最大独立集大小(即最大独立集的节点个数)以及最大独立集个数。

第四行 pp 个整数,表示最大独立集的点集。

如果有多个满足要求的点集,输出任意一组即可。

6 7
1 2
2 3
3 4
4 1
3 5
5 4
2 6
3 1
3 4 5
3 2
1 3 6

提示

样例解释

GG 的最大团分别为 {3,4,5}\{3,4,5\}

GG 的最大独立集分别为 {1,3,6},{1,5,6}\{1,3,6\},\{1,5,6\}

数据范围

对于全部数据:1n501\leq n\leq 500m12250\leq m\leq 12251u,vn1\leq u,v\leq n