请教一道关于子树(图)匹配的 OJ 题

fourstring 2019-12-12 187

题目原文如下:


Description

给定两棵无根树,问第一棵树是否包含第二棵树。

Input Format

此题仅有一个测试点,

多组数据,第一行为一个数表示数据组数。

对于每组数据:

第一行为 N 表示第一棵树的点数

接下来 N-1 行描述第一棵树的边

接下来一行为 M 表示第二棵树的点数

接下来 M-1 行描述第二棵树的边

Output Format

对于每组数据,若第一棵树包含第二棵树则输出 YES 否则输出 NO

Sample Input

2
5
1 2
1 3
3 4
3 5
4
1 4
2 4
3 4
4
1 2
1 3
1 4
4
1 2
2 3
3 4

Sample Output

YES
NO

Hint

n,m<=100 ; 150 组数据


这题和一般子树匹配问题不同的地方在于输入数据的格式,首先输入的树是无根的,实际上相当于一个图的生成树;其次两棵树之间结点的对应关系并没有给定,所以无法通过简单前序+中序遍历比较的方式来确定第一棵树是否包含了第二棵树。

从图的角度来看这似乎是一个子图匹配(Subgraph Matching)问题,查了下 Google 只找到了一些关于子图同构(Subgraph isomorphism)的资料,如 Ullmann 算法和 VF2 算法,但它们都要求两图之间结点的映射是给定的,但事实上对于本题如果能找到这样一个映射关系,剩下的也并不成为问题。

另外我还找到了本题的一份 AC 代码,不过带有明显的 OI 风格,由于我个人没有相关经验所以调试了很久也没理解这段代码的写法,链接如下:

  • https://git.codingcafe.org/Contest/SJTUOJ/blob/0c4dde00abbdcc0933118e9622c66b7a76231cb5/P1314/SJTUOJ_P1314.cpp

请问是否有大佬指点一下本题的简单思路或者能大致解释一下这段 AC 代码的逻辑?感激不尽!

最新回复 (0)
  • 游客
    2
返回