V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
fourstring
V2EX  ›  问与答

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

  •  
  •   fourstring · 2019-12-12 19:43:25 +08:00 · 1056 次点击
    这是一个创建于 1567 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目原文如下:


    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 风格,由于我个人没有相关经验所以调试了很久也没理解这段代码的写法,链接如下:

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

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3258 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 11:30 · PVG 19:30 · LAX 04:30 · JFK 07:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.