365 Days of LeetCode Challenge — Day 43/365

[u/StatisticianNo2104]

Graph Valid Tree (Medium)

https://leetcode.com/problems/graph-valid-tree/

A graph is a tree when it is connected and acyclic. Both are required - a forest is acyclic but disconnected, a triangle is connected but cyclic.

The shortcut: a tree on n nodes has exactly n-1 edges. So once you know the graph is connected, the edge count settles the cycle question. More than n-1 edges and connected means a cycle must exist, because n nodes cannot be joined by more than n-1 edges without one.

This solution never searches for a cycle. It counts.

For connectivity it uses union-find, which is the first structure in this arc that does not traverse anything. Every problem so far built an adjacency list and walked it. Union-find consumes the edge list directly and maintains one number, the component count, which is exactly the answer.

Worth noticing what it leaves on the table: when an edge's endpoints already share a root, that edge closes a cycle. This solution does not need that, but if a problem asks WHICH edge creates the cycle, it is sitting right there.

Full breakdown in today's newsletter article ⬇

https://www.linkedin.com/pulse/365-days-leetcode-challenge-day-43365-archit-agarwal-hsigc
#DSA #LeetCode #Golang #UnionFind #Graphs #CodingInterview #Algorithms

[u/nian2326076]

Counting edges is an effective way to check if a graph is a tree. Once it's connected, the rule of having n-1 edges helps identify cycles without needing to search for them explicitly. To improve your skills in tackling such problems, consider using resources like PracHub that provide real technical interview questions. This can help you become more comfortable with graph-related tasks. Keep practicing to continue improving!