Адамдар — төбелер, қабырғалар — симпатия, командалар арасындағы симпатия — командалар арасындағы қашықтық болсын. Мәселенің идеясы қарапайым: командаларды СНМ-де сақтау және олардың арасындағы қашықтық \(W\) мәнінен асқанда командаларды бір-біріне біріктіру. Әрбір команда бір төбе болады, бастапқыда әр төбе өзі команда болып табылады. Дегенмен, осы алгоритмді мұқият іске асыру қажет.

Әрбір біріктіруден кейін төбелер саны кем дегенде \(1\)-ге азаятынын байқайық. Демек, осындай біріктірулер саны \(n\)-нан аз болады. Сондықтан біз біріктіруді сызықтық алгоритммен жүзеге асыра аламыз. Қабырғалардың салмағы \(W\) мәнінен асатындарын кезекке қоямыз — олардың ұштарын міндетті түрде біріктіруіміз қажет. Одан кейін, кезек ретімен келесі қабырғаның \((a,b)\) ұштарын біріктіріп отырамыз: \(b\)-дан жаңа қабырғалар қосылғанын ескере отырып, \(a\)-дан қалғандарына дейінгі қабырғалардың салмақтарын қайта есептейміз \(O(n)\) уақытта. Егер жаңа қабырғалардың салмақтары \(W\) мәнінен асатын болса, оларды кезекке саламыз.

Жұмыс уақыты: \(O(n^2)\).

Пусть люди – вершины, ребра – симпатия, симпатия между командами - дистанция между командами. Идея задачи проста: хранить команды в СНМе и объединять команды в одну когда дистанция между ними превышает \(W\). Каждая команда будет одной вершиной, изначально каждый вершина сама по себе команда. Однако требуется аккуратная реализация этого алгоритма.

Заметим, что после каждого объединения количество вершин уменьшается хотя бы на \(1\). Значит таких объединений будет меньше \(n\). Значит мы может Объединять линейным алгоритмом. Заведем очередь ребер, вес которых превышает \(W\) – их концы мы обязаны объединить. Далее будем в порядке очереди объединять концы очередного ребра \((a,b)\): пересчитаем веса ребер из \(a\) в остальные с учетом новых ребер из \(b\) за \(O(n)\). Если новые веса ребер превышают \(W\), закинем их в очередь.

Время работы: \(O(n^2)\).