We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Components in a graph
Components in a graph
Sort by
recency
|
183 Discussions
|
Please Login in order to post a comment
2 ways to solve this problem: - Use DFS: - Use Union Find data structure
See my solution here: https://github.com/tuphan22028238/DSA/tree/main/ComponentInGraph
C#:
Python solution
Java Solution
I came to this problem right after the "disjoint sets" problem, in which I learned the DSU data structure and implemented it for that problem.
Interestingly, I started out trying to use my DSU data structure for this problem - but changed approaches to something else (balanced binary search trees) because I neglected to consider an important constraint:
This problem's inputs bg[i][j] are all constrained to be >= 1 <= n * 2. Because I didn't consider this, I didn't see an opportunity to use
make
on a static set of nodes.In any event, there are some test cases that cause data structures like a BST to become skewed to worse case - timing me out, which I considered solving with a red-black tree implementation. At that point I suspected I was overcomplicating things, and revisited the idea of using a vanilla DSU for this, at which point it occured to me I could
make
an initial forest of n * 2 nodes, insert all b[i][j] usingunion
, and ultimately usingfind
on each node to get the size of the connected graphs from the representative of each set.Here's a python solution that passed the test cases.