LC: 323. Number of Connected Components in an Undirected Graph
https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
The Essence:
Wenn eine Menge von Knoten in einem zusammenhängenden (connected) Komponent, impliziert diese Tatsache 2 andere Tatsachen:
Man kann alle Knoten des Komponents von irgendwelchem Knoten angefangen traversieren.
Ein gemeinsamer Wurzelknoten für die Knoten eines zusammenhängenden Komponenten kann ausgewählt werden.
Details:
Die erste Tatsache weist darauf hin, dass man aus den eingegebenen Kanten den Graphen konstruieren und dann durch Tiefensuche und Breitensuche des jeweiligen Knoten die Anzahl der Komponente zählen kann.
Die zweite Tatsache gibt eindeutig an, dass wir die Union-Find-Technik anwenden können, wobei die Anzahl der Komponente dekrementiert wird, wenn eine Kante zwei vorher nicht zusammenhängende Komponente verbindet.
Solutions and Further Explanation: https://github.com/spiralgo/algorithms/pull/200
Default Code:
Last updated