54 . 仙人掌判定問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (29/29)

Submission's AC Ratio

68.8% (53/77)

Tags

ioicamp ioicamp-2024

Description

給你一張無向簡單連通圖，請你判斷他是不是仙人掌。

仙人掌的定義是對於一張圖上的任意一條邊 $e$，$e$ 至多只會出現在一個環上。

Input Format

輸入第一行包含兩個非負整數 $N$, $M$，代表點和邊的數量。

接下來的 $M$ 行，第 $i$ 行包含兩個正整數 $a_i$, $b_i$，代表節點 $a_i$ 和節點 $b_i$ 之間有一條邊。

  • $1 \le N \le 2 \times 10^ 5$
  • $0 \le M \le 5 \times 10^ 5$
  • $1 \le a_i, b_i \le N$

Output Format

若該圖是一棵仙人掌，請輸出 Yes，反之請輸出 No。

Sample Input 1

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

Sample Output 1

Yes

Sample Input 2

5 7
1 2
2 3
3 1
3 4
4 5
5 3
5 2

Sample Output 2

No

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~22 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
Submit
Back to Top