D. Almost Acyclic Graph

Codeforces

IDCF915D

Time1000ms

Memory256MB

Difficulty—

dfs and similargraphs

English · Original

Chinese · Translation

Formal · Original

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). ## Input 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_). ## Output If it is possible to make this graph acyclic by removing at most one edge, print _YES_. Otherwise, print _NO_. [samples] ## Note In the first example you can remove edge , and the graph becomes acyclic. In the second example you have to remove at least two edges (for example, and ) in order to make the graph acyclic.

给定一个有向图，包含 #cf_span[n] 个顶点和 #cf_span[m] 条边（每条边都是有向的，只能沿一个方向遍历）。你可以最多删除其中一条边。能否通过删除至多一条边使该图变为无环图？一个有向图被称为无环图，当且仅当其中不包含任何环（一个非空路径，起点和终点为同一顶点）。第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 500]，#cf_span[1 ≤ m ≤ min(n(n - 1), 100000)]）——分别表示顶点数和边数。接下来 #cf_span[m] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]，表示一条从顶点 #cf_span[u] 指向顶点 #cf_span[v] 的有向边（#cf_span[1 ≤ u, v ≤ n]，#cf_span[u ≠ v]）。每个有序对 #cf_span[(u, v)] 最多出现一次（从 #cf_span[u] 到 #cf_span[v] 的有向边至多一条）。如果可以通过删除至多一条边使该图变为无环图，则输出 _YES_；否则输出 _NO_。在第一个示例中，你可以删除边，图将变为无环图。在第二个示例中，你必须删除至少两条边（例如，和）才能使图变为无环图。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 500]，#cf_span[1 ≤ m ≤ min(n(n - 1), 100000)]）——分别表示顶点数和边数。接下来 #cf_span[m] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]，表示一条从顶点 #cf_span[u] 指向顶点 #cf_span[v] 的有向边（#cf_span[1 ≤ u, v ≤ n]，#cf_span[u ≠ v]）。每个有序对 #cf_span[(u, v)] 最多出现一次（从 #cf_span[u] 到 #cf_span[v] 的有向边至多一条）。 ## Output 如果可以通过删除至多一条边使该图变为无环图，则输出 _YES_；否则输出 _NO_。 [samples] ## Note 在第一个示例中，你可以删除边，图将变为无环图。在第二个示例中，你必须删除至少两条边（例如，和）才能使图变为无环图。

Let $ G = (V, E) $ be a directed graph with $ |V| = n $, $ |E| = m $. **Goal:** Determine whether there exists an edge $ e \in E $ such that the graph $ G' = (V, E \setminus \{e\}) $ is acyclic, or whether $ G $ is already acyclic (i.e., remove zero edges). **Formal Statement:** Does there exist a subset $ E' \subseteq E $ with $ |E'| \leq 1 $ such that $ (V, E \setminus E') $ is a directed acyclic graph (DAG)? Equivalently: - If $ G $ is already acyclic, return YES. - Else, for each edge $ e \in E $, check whether $ G \setminus \{e\} $ is acyclic. If any such $ G \setminus \{e\} $ is acyclic, return YES; otherwise, return NO.

Samples

Input #1

Output #1

YES

Input #2

Output #2

NO

API Response (JSON)

{
  "problem": {
    "name": "D. Almost Acyclic Graph",
    "description": {
      "content": "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 a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF915D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个有向图，包含 #cf_span[n] 个顶点和 #cf_span[m] 条边（每条边都是有向的，只能沿一个方向遍历）。你可以最多删除其中一条边。\n\n能否通过删除至多一条边使该图变为无环图？一个有向图被称为无环图，当且仅当其中不包含任何环（一个非空路径，起点和终点为同一顶点）。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 500...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ G = (V, E) $ be a directed graph with $ |V| = n $, $ |E| = m $.\n\n**Goal:** Determine whether there exists an edge $ e \\in E $ such that the graph $ G' = (V, E \\setminus \\{e\\}) $ is acyclic, or w...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments