TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2128
  • 题目
  • P2128简单图论问题
    限制 : 时间限制 : 10000 MS   空间限制 : 524288 KB
    评测说明 : 2s,512MB
    问题描述

    给定一个 \(n\) 个节点 \(m\) 条边的简单有向无环图,对于一条边 \(u\to v\) ,判断 \(u,v\) 之间是否存在一条不经过这条边的路径。

    输入格式

    第一行两个整数 \(n,m\) ,即节点数和边数。

    接下来 \(m\) 行,每行两个整数 \(u,v\) ,表示一条有向边 \(u\to v\)

    输出格式

    输出 \(m\) 行,表示每条边的判断结果,路径存在输出 Yes ,不存在输出 No

    样例输入

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

    样例输出

    No
    No
    No
    No
    No
    Yes

    提示

    对于0%的数据, \(n\leq 1000\)\(m\leq 3000\)

    对于100%的数据, \(n\leq 100000\)\(m\leq 300000\)