12
votes
Accepted
Printing the bits of an integer using bitfields and union
Avoid global variables - there's no need for t and v to exist outside main().
Always check ...
- 81.8k
8
votes
Accepted
Disjoint set in Haskell
Naming
While it's usually not a big deal to have names like d and d' flying around, seeing ...
- 685
7
votes
Accepted
Disjoint-set data structure (C++)
Here are some things that may help you improve your program.
Use include guards instead of #pragma once
The use of ...
- 66.6k
5
votes
Printing the bits of an integer using bitfields and union
In addition to @Toby Speight's answer.
There are only four types allowed for a bit field. There are the follows: signed int, ...
- 405
5
votes
Accepted
How Rusty is my generic union-find implementation?
Since you never delete nodes, and if you do not intend to implement element deletion, you may fare better with alternatives for storing nodes, such as ...
- 1,404
5
votes
Accepted
Performance of C++ Union-Find solution is strangely poor
This is a really interesting problem! Here are some things I noticed about your implementation.
Performance
Looking at a profile of your code (compiled with llvm on macOS High Sierra with Xcode 9.2), ...
- 11.8k
4
votes
Accepted
4
votes
Graph library including minimum spanning tree using Kruskal's Algorithm
I see a number of things that may help you improve your program.
Don't abuse using namespace std
Putting using namespace std at ...
- 66.6k
4
votes
Accepted
Swiftly counting rooms in a floor plan
Not a full review, I don’t know Swift at all. I just wanted to comment on the union-find implementation.
I’ve seen this a lot, keeping track of the rank, it never found it useful. When you are ...
- 6,247
4
votes
Disjoint set in Haskell
Control.Lens makes the record syntax pain go away. non unmakes make, and eliminates the ...
- 3,724
4
votes
Union-Find in C++
Welcome to Code Review.
union_find.cpp looks like a header-only library. It's thus strange its not named like a header.
Make all single-argument-constructors ...
- 19.3k
3
votes
Accepted
K-clustering algorithm using Kruskal MST with Disjoint Set in place to check for cycles
Use your own typedefs
I see this code:
...
- 61.7k
3
votes
Accepted
Integer index based Union Find with path compression strategy
Using two arrays of int
That's nice. There is a tendency to use Node objects that refer to each other by address, which still ...
- 10.8k
3
votes
Printing the bits of an integer using bitfields and union
I agree with most of the suggestions from @TobySpeight, except for the loop variable. Consider:
...
- 65.6k
3
votes
Weighted union-find with path compression in Python 3
unite should check if p and q are in the same set already and do nothing in that case.
Using ...
- 10.4k
3
votes
Union Find implementation
Consider an iterative path compression design for root. The recursive version uses more memory for stack frames. Typical iterative versions follow the path one at a ...
- 121
3
votes
Accepted
Find cycles in Graph using Union Find Algorithm on Adjacency List
addnode(self, key1, key2, edge=0)
The parameter edge is not used. Either remove it, or use it, but keeping it with a default ...
- 34k
3
votes
Accepted
Kruskal MST algorithm
General
This should probably be three separate classes, unless there's some compelling reason you haven't shared to wrap WeightedEdge and ...
- 6,626
3
votes
Accepted
Weighted Union-Find class
Documentation
Docstrings are for users of the class. Docstrings should explain what is being done and returned. Currently your docstrings explain how it is being done, which should be comments.
...
- 1,493
3
votes
C++ two-phase path-compression quick-union union find over indices
Honestly, it seems cumbersome.
First, using a std::size_t instead of a std::optional<std::size_t>, and making the roots ...
- 19.3k
2
votes
Finding the size of the largest connected component in a graph
About the first approach:
I would initialize max_size to 0 instead of Integer.MIN_VALUE, ...
- 2,138
2
votes
Disjoint-set data structure (C++)
Prefer using operator[] instead of at()
The member function at() performs bounds checking, ...
- 61.7k
2
votes
Leetcode 1584. How to make my Kruskal&Union Find algorithm faster?
Your solution already seems to be implemented (rather) efficiently. My only advice is to rename Find and Union to ...
- 29.8k
2
votes
Accepted
Union find using unordered map and templates in C++
Overall, that looks good to me. A few nitpicks, however, follow:
Advice 1
...
- 29.8k
2
votes
Different approach Union Find
First of all, I like the idea and the implementation.
I have refactored it a bit and came up with that:
isConnected: Extract connection[a] and connection[b] in local variables and simplify the ...
- 159
2
votes
Disjoint-set data structure (C++)
High-level design:
All the other answers went over the minutiae quite sufficiently, but this is where about 66% savings are easily achieved.
There are some questionable design-decisions, which ...
- 19.3k
2
votes
Accepted
Percolation threshold simulation using C++
Use std::size_t for sizes, counts and indices
You are using int to store sizes, counts and indices, however an ...
- 61.7k
1
vote
Different approach Union Find
As soon as you said it's linear time, it was clear that something is wrong. Quick glance at the code showed no loops or recursion, so it was clear that it's indeed linear time and that your algorithm ...
- 3,991
1
vote
Union find using unordered map and templates in C++
There is no need for unordered maps, especially not for two of them. Also, since you are dealing with indices and counts, you should make them std::size_t, not <...
- 2,855
Only top scored, non community-wiki answers of a minimum length are eligible