P1536 Village-to-Village Connectivity

A city surveyed its urban transportation and obtained a current list of roads between towns. The list enumerates which pairs of towns are directly connected by a road. The goal of the city’s "Village-to-Village Connectivity" project is to ensure that any two towns in the city can reach each other (there does not have to be a direct road between them, as long as they are mutually reachable). Please compute the minimum number of additional roads that still need to be built.

The input contains multiple test cases. For each test case, the first line gives two positive integers separated by a space, the number of towns $n$ and the number of roads $m$. The following $m$ lines describe the $m$ roads; each line gives a pair of positive integers separated by a space, which are the labels of the two towns directly connected by that road. For simplicity, towns are labeled from $1$ to $n$. Note: multiple roads may exist between the same pair of towns. At the end of the input, there is a line containing a single integer $0$, which marks the end of the testdata.

For each test case, output a single integer on its own line: the minimum number of additional roads required.

Constraints For $100\%$ of the testdata, $1 \le n < 1000$. Translated by ChatGPT 5