When Kruskal considers edge (u, v) and `find(u) == find(v)`, the algorithm
Askips (u, v) because adding it would create a cycle
Balways accepts (u, v) because the find succeeded
Crebuilds the tree from scratch
Dcalls Dijkstra to find an alternative path
Answer & Solution
Correct answer: A. skips (u, v) because adding it would create a cycle
If find(u) and find(v) return the same root, u and v are already in the same connected component of the partial MST. Adding (u, v) would create a cycle, violating tree-ness. Skip. When the roots differ, the edge bridges two components, so accept and call union(u, v) to merge them.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for