304805: CF915D. Almost Acyclic Graph

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Almost Acyclic Graph

题意翻译

给定一个 $n$ 个顶点,$m$ 条边的有向图。你允许从其中去掉最多一条边。 你能够去掉最多一条边就让这个图无环吗?我们称一个有向图无环,当且仅当它不包含一个环(起点和终点相同的路径)。 #### 输入格式: 第一行两个正整数 $n,m$($2\le n\le 500,1\le m\le min(n(n-1),10^5))$,代表图的顶点数和边数。 接下来 $m$ 行,每行两个数 $u,v$,表示有一条从 $u$ 到 $v$ 的有向边($1\le u,v\le n,u\ne v$)。一对 $(u,v)$ 最多出现一次。 #### 样例说明: 第一个样例中,去掉 $2\to 3$ 的边即可。 第二个样例中,需要至少去掉两条边(例如 $2\to 1$ 和 $2\to 3$)才能让这个图变成无环图。 Translated by @小粉兔

题目描述

You are given a [directed graph](https://en.wikipedia.org/wiki/Directed_graph) consisting of $ n $ vertices and $ m $ edges (each edge is directed, so it can be traversed in only one direction). You are allowed to remove at most one edge from it. Can you make this graph [acyclic](https://en.wikipedia.org/wiki/Directed_acyclic_graph) by removing at most one edge from it? A directed graph is called acyclic iff it doesn't contain any cycle (a non-empty path that starts and ends in the same vertex).

输入输出格式

输入格式


The first line contains two integers $ n $ and $ m $ ( $ 2<=n<=500 $ , $ 1<=m<=min(n(n-1),100000) $ ) — the number of vertices and the number of edges, respectively. Then $ m $ lines follow. Each line contains two integers $ u $ and $ v $ denoting a directed edge going from vertex $ u $ to vertex $ v $ ( $ 1<=u,v<=n $ , $ u≠v $ ). Each ordered pair $ (u,v) $ is listed at most once (there is at most one directed edge from $ u $ to $ v $ ).

输出格式


If it is possible to make this graph acyclic by removing at most one edge, print YES. Otherwise, print NO.

输入输出样例

输入样例 #1

3 4
1 2
2 3
3 2
3 1

输出样例 #1

YES

输入样例 #2

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

输出样例 #2

NO

说明

In the first example you can remove edge ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF915D/f1138b32236a89525fad2b8c02b9cbfbd546dfad.png), and the graph becomes acyclic. In the second example you have to remove at least two edges (for example, ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF915D/7480c546ca7ee72615c3ded7d769355b1c864f93.png) and ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF915D/f1138b32236a89525fad2b8c02b9cbfbd546dfad.png)) in order to make the graph acyclic.

Input

题意翻译

给定一个 $n$ 个顶点,$m$ 条边的有向图。你允许从其中去掉最多一条边。 你能够去掉最多一条边就让这个图无环吗?我们称一个有向图无环,当且仅当它不包含一个环(起点和终点相同的路径)。 #### 输入格式: 第一行两个正整数 $n,m$($2\le n\le 500,1\le m\le min(n(n-1),10^5))$,代表图的顶点数和边数。 接下来 $m$ 行,每行两个数 $u,v$,表示有一条从 $u$ 到 $v$ 的有向边($1\le u,v\le n,u\ne v$)。一对 $(u,v)$ 最多出现一次。 #### 样例说明: 第一个样例中,去掉 $2\to 3$ 的边即可。 第二个样例中,需要至少去掉两条边(例如 $2\to 1$ 和 $2\to 3$)才能让这个图变成无环图。 Translated by @小粉兔

加入题单

上一题 下一题 算法标签: