图的团分割最小块数_

$\hspace{15pt}$

题目来源：https://atcoder.jp/contests/abc187/tasks/abc187_f

给定一个简单无向图，包含 $N$ 个顶点与 $M$ 条边。顶点编号为 $1,2,\dots,N$ ，第 $i$ 条边连接顶点 $A_i$ 与顶点 $B_i$ 。允许从图中删除任意条边（可为 $0$ 条）。

$\hspace{15pt}$ 定义删除后得到的图的每个连通分量必须满足：对该分量内的任意一对不同顶点 $(a,b)$ ，若 $a<b$ ，则删边后图中存在一条直接连接 $a$ 与 $b$ 的边。等价地，删边后每个连通分量的诱导子图为完全图（团）。
$\hspace{15pt}$ 在满足上述条件的所有删边方案中，求图的连通分量数量的最小可能值。

$\hspace{15pt}$ 【名词解释】
$\hspace{23pt}\bullet\,$ 简单无向图：简单无向图指不含自环与重边的无向图。
$\hspace{23pt}\bullet\,$ 连通分量：连通分量指图中一个极大连通子图；任意两个顶点均有路径相连，且无法再加入其他顶点保持连通。
$\hspace{23pt}\bullet\,$ 团（完全图）：团指一组顶点的诱导子图为完全图，即该组顶点之间的每一对都存在边相连。

$\hspace{15pt}$ 第一行输入两个整数 $N,M$ ，表示顶点数与边数，满足 $1\leqq N\leqq 18$ ， $0\leqq M\leqq \frac{N(N-1)}{2}$ 。
$\hspace{15pt}$ 接下来 $M$ 行，每行输入两个整数 $A_i,B_i$ ，表示一条无向边，满足 $1\leqq A_i<B_i\leqq N$ ，且任意两条输入边不同，即 $(A_i,B_i)\neq (A_j,B_j)$ 对所有 $i\neq j$ 。
$\hspace{15pt}$ 所有输入均为整数。

图的团分割最小块数

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题