首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >蓝桥--版本分支

蓝桥--版本分支

作者头像
用户3470542
发布2019-10-23 17:23:15
3070
发布2019-10-23 17:23:15
举报
文章被收录于专栏:算法半岛算法半岛

题目描述

小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(branch)但是从未发生过合并(merge)。现在这个项目的代码一共有N个版本,编号1~N,其中1号版本是最初的版本。除了1号版本之外,其他版本的代码都恰好有一个直接的父版本;即这N个版本形成了一棵以1为根的树形结构。

如下图就是一个可能的版本树:

1
   / \
  2   3
  |  / \
  5 4   6

现在小明需要经常检查版本x是不是版本y的祖先版本。你能帮助小明吗?

输入

第一行包含两个整数N和Q,代表版本总数和查询总数。 以下N-1行,每行包含2个整数u和v,代表版本u是版本v的直接父版本。 再之后Q行,每行包含2个整数x和y,代表询问版本x是不是版本y的祖先版本。

对于30%的数据,1 <= N <= 1000 1 <= Q <= 1000 对于100%的数据,1 <= N <= 100000 1 <= Q <= 100000

输出

对于每个询问,输出YES或NO代表x是否是y的祖先。

【样例输入】

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

【样例输出】

YES
YES
NO
NO
NO

分析

这个题目需要了解深度优先遍历(dfs),如果对dfs不太熟悉的小伙伴可以查看数据结构与算法-深度优先搜索。了解了dfs后,这个题目的难度就不大了。

分析题目重点样例输入,第一行输入6和5,其中6表示第2行到第6行为组成版本的行数,5表示倒数5行为校验版本的行数。对于样例中的输入构建成二叉树如下所示:

根据图中的版本分支关系,不难得出样例输出结果。

java代码如下所示:

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static Map<Integer,Integer> map=new HashMap<Integer,Integer>();

    static boolean dfs(int x,int y){//x是不是y的祖先
        if(x==y)
            return true;
        else if(map.containsKey(y)){
            int father=map.get(y);
            if(father==x)
                return true;
            else
                return dfs(x,father);
        }
        else
            return false;
    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt(),q=in.nextInt();
        // u是v的直接父版本,注意构建HashMap时,key为v, value为u
        for(int i=1;i<n;i++){
            int u=in.nextInt();
            int v=in.nextInt();
            map.put(v,u);
        }
        // 判断x是不是y的祖先
        for(int i=0;i<q;i++){
            int x=in.nextInt(),y=in.nextInt();
            if(dfs(x,y))
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}

输出结果:

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-10-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法半岛 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 输入
  • 输出
  • 分析
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档