Разбор добавил Иван Смирнов

Решение основано на системе непересекающихся множеств (DSU) городов. Два города принадлежат одному и тому же множеству тогда и только тогда, когда они достижимы друг из друга по уже построенным мостам. Введем счетчик текущего количества множеств, изначально равный n. Изначально в каждом множестве находится только один город. При считывании моста (x, y) проверим, находятся ли города x и y в одном множестве. Если нет, то объединим содержащие их множества и уменьшим счетчик на 1. Как только счетчик станет равным 1 (то есть все города будут принадлежать одному множеству), выведем количество считанных мостов.