#2300. isomorphism
isomorphism
isomorphism
题目描述
简化树的同构 (isomorphism.pas/c/cpp)
【问题描述】 一个无向树的度数为2 的结点称为假结点,其它结点称为真结点。一个无向树的简化树 其结点由原树的全体真结点组成,两个真结点之间有边当且仅当它们在原树中有边,或者在 原树中有一条联结这两个结点的路,其中间节点全是假结点。两个无向树各自的简化树如果 同构,即存在结点之间的一一对应,使得在一个树中的任意两个结点之间有边当且仅当它们 的对应结点在另一个树中有边,则称原来的两个无向树实质同构。给定若干个无向树,将相 互实质同构的无向树只保留一个其余删除。统计剩下的相互不实质同构的无向树个数,并将 它们的简化树结点个数从小到大输出。
【输入格式】 第一行只有一个正整数m,后面依次输入m 个无向树,每个无向树先用一行输入结点个 数n,结点就用1 到n 表示,然后用n-1 行输入n-1 条无向边,每行有两个1 到n 之间的不 同的正整数,用一个空格隔开,代表这两个结点之间有无向边。两个树之间无空行。 【输出格式】 第一行输出一个正整数,即输入中不计实质同构包含无向树的个数m0(1<=m0<=m)。第 二行包含不严格递增的m0 个正整数,表示这m0 个无向树的简化树结点个数。相邻两数用一 个空格隔开。 【样例输入】 isomorphism.in 2 4 1 4 2 4 3 4 5 1 3 2 3 3 4 4 5 【样例输出】 isomorphism.out 1 4 【数据规模】 30%的数据满足:2<=m<=10, 2<=n<=10 60%的数据满足:2<=m<=20, 2<=n<=300 100%的数据满足:2<=m<=20, 2<=n<=10000
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2
4
1 4
2 4
3 4
5
1 3
2 3
3 4
4 5
1
4