Pro.ID1925 Title算法设计例题:最大团(回溯、分枝限界) Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1925 AC228 Submit740 Ratio30.81% 时间&空间限制描述给定无向图G=(V,E)。如果UV,且对任意u, v ∈ U 有 (u,v) ∈ E,则称U是G的完全子图。G的完全子图U是G的团,当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。 输入输入的第一行为测试样例的个数T ,接下来有T个测试样例。每个测试样例的第一行是 顶点数n 和 边数m ( n ≤ 20,m ≤ 400 ),接下来m行,每行两个整数u和v,表示顶点u和v之间有一条边相连。( 1 ≤ u < v ≤ n )。 输出Description 给定无向图G=(V,E)。如果UV,且对任意u, v ∈ U 有 (u,v) ∈ E,则称U是G的完全子图。G的完全子图U是G的团,当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。 Input 输入的第一行为测试样例的个数T ,接下来有T个测试样例。每个测试样例的第一行是 顶点数n 和 边数m ( n ≤ 20,m ≤ 400 ),接下来m行,每行两个整数u和v,表示顶点u和v之间有一条边相连。( 1 ≤ u < v ≤ n )。 Output 对应每个测试样例输出两行,第一行格式为"Case #: M",其中'#'表示第几个测试样例(从1开始计),M为最大团顶点数。 Sample Input 1 Sample Output Case 1: 3 Author 样例输入1 样例输出Case 1: 3 提示作者 |