search

spiralgo / algorithms

We voluntarily solve algorithm problems on this repo.
24 stars 7 forks source link

323. Number of Connected Components in an Undirected Graph #31

Closed altay9 closed 3 years ago

altay9 commented 3 years ago

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph

Undirected Graph, node'ların belli bir yönü olmaması demektir. Bu yüzden [0 ,1] bağlantısı ile [1, 0] bağlantısı aynı şeydir ve 0 numaralı node'dan, 1 numaralı node'a bir bağlantı olduğunu gösterir. Bu bağlantı çizgisine kenar (edge) denir.

Bize bu kenarların bir array'i (int[][] edges) ve node sayısı (n) veriliyor.

Bu bağlantıları kullanarak oluşan bileşen sayısını bulun diyor.

Meselâ her bir node'u bir lego parçası olarak düşünelim. Bu array (int n, int[][] edges), hangi legonun hangisi ile bağlandığını gösteriyor. Sonuçta ortaya birden fazla "büyük lego" (bileşen, component) çıkabileceği gibi, tek bir büyük lego da çıkabilir.

İşte bu ortaya çıkan lego sayısı soruluyor.

ErdemT09 commented 3 years ago

Bu soru bana biraz küme birleştirme konusunu ve Kruskal algoritmasını hatırlattı. Şu soru öyle.

altay9 commented 3 years ago

Evet. Aynı şekilde, şu sorular da Kruskal'ın temeli olan Union-Find ile çözülebilir:

  1. The Earliest Moment When Everyone Become Friends https://github.com/spiralgo/algorithms/issues/185

  2. Lexicographically Smallest Equivalent String https://github.com/spiralgo/algorithms/issues/186