771 . 小黃瓜傳送門

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (4/4)

Tags

apcsc apcsc-graph

Description

小黃瓜是蔬菜界的最高神，統領非常多的世界。這些世界之間有一些傳送門可以讓不同世界互相通行。小黃瓜在閒閒沒事做的時候隨便亂設了幾組傳送們，然而他發現還是有一些世界沒辦法互相通行。小黃瓜現在不想動腦，請你幫小黃瓜算一下他最少還要再設幾組傳送門才能讓所有世界互通，如果你算對了他也許會送你幾根小黃瓜作為謝禮。

註：如果 A 世界與 B 世界互通，B 世界與 C 世界互通，那麼 A 世界與 C 世界互通。

Input Format

輸入第一行有兩個整數 $N, M$，$N$ 代表世界的數目、$M$ 代表傳送門的數目 (組)。
接下來有 $M$ 行，每一行有兩個數字 $a, b$，$a, b$ 是世界的編號，而傳送門的兩端分別被設在 $a$ 世界與 $b$ 世界。

限制：

  • $1 \leq N, M \leq 10^ 5$
  • 世界的編號從 $1$ 到 $N$

Output Format

輸出一個數字，代表小黃瓜還需要設幾組傳送門才能讓所有世界互通。

Sample Input 1

3 3
1 1
1 2
2 1

Sample Output 1

1

Hints

Problem Source

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
Submit
Back to Top