Hackerrank: Spanning Tree Fraction

April 13, 2017

Problem statement

Introduction

Julia likes to work on spanning tree algorithm, even though it is hard algorithm, but Julia did spend some time on the algorithm before. So, it is also a good practice to review previous contests related algorithms.

Julia started to read minimum spanning tree, understand why union set is better than DFS algorithm to detect cycle in the tree algorithm.

Minimum Spanning Tree

Here is the tutorial she studied for the algorithm.

minimum spanning tree -  April 13, 2017 

Hackerearth.com -> graph -> minimum spanning tree -> tutorial 

Kruskal's algorithm - 

Learn the algorithm - using disjoint set / not DFS 

check how it is not connected? Using DFS algorithm to search - O(V + E) 

Value of friendship

Code review of algorithm "value of friendship" is here.

Kruskal's algorithm

GeeksforGeeks article

Code preparation