4 kyu
Strongly connected components
118user5697006
Loading description...
Algorithms
Data Structures
Performance
Graph Theory
.avif)
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
Funny kata...
Java translation, please review.
Nice kata!
Needed to brush up on my graph skills, thanks :D
Nice kata, thank you. Solution is pretty by-the-book because this is a well know graph problem. The description could be improved, the example is hard to follow because letters are associated to indexes in a different order (that
(0, 1, 2, 3, 4, 5, 6, 7) = (a, b, e, f, c, g, d, h)). Just use numbers to label the nodes please, or do not change the order of the letters.This comment has been hidden.
Maybe the output should be a set of strongly connected components, since in the description there is no instruction given on how to order the components.
Order doesn't matter in this kata, and sets are not hashable.
This comment has been hidden.
oops
:/ (always the same problems... python is a nightmare about that)
Hehe... I had to take the "dirtiest" trick. Try to hack kata now ;)
"Hacked":
|Θ_v_Θ|
Oh, I just noticed someone recently became a mod.
\'o'/
Congrats.
@Rail-Gun: I already went through this kind of "shit". It's close to impossible, to do it completely, in python. I built a module forbidder, but it's not perfect (I know Unnamed broke it again some time ago, but I don't have the link anymore, so I didn't update it)
edit: it's rather "team member" than mod, for now (and I'm not the onlyone, it's just to make visible what has been done some months ago already). ;)
@Blind4Basics I can recall this version, I don't remember if this is the most recent one.
Hi,
missing fixed tests (would be good as sample tests):
(no idea about the reason, for now...)
Just a feedback : not familiar with adjacency lists, I had a bit trouble with the input list before I finally understood that the values of the vertices in your adjacency list are the indices of the input list and the list of linked vertices for a given index or vertex ,are the elements of the sublist ....
Thanks for feedback, аdded more details to the description.
Approved.
Hooray!)
(raising this as an issue in order to avoid premature approval)
Are you aware of this solution? As that might effect the ranking of the kata.
I added test for using scipy, now such cheating solutions will not pass.
Thanks for disabling that, I think this should be a 4 kyu.
Perhaps I'll approve this in a while after making minor changes to description, and as of now the image is violating copyright issues of programiz.
Performance requirements are not mentioned anywhere.
If you mean the asymptotics of the algorithm, then this information will be a spoiler
Write tests using the test framework instead of plain
assert.Different solutions can output strongly connected components in different sequences, so I need to iteratively check strongly connected components for occurrence in the response. I haven't decided to use sorting for tests yet, because it will take a long time. If you know a way to do it better using the framework, I will be happy to find out
just use
test.expect(isCorrect, "meaningful error message here")instead of assertThank you, fixed (and changed tests :) )
How many tests are there?
10000 random tests with graphs on 10-30 vertices and 0-4 outgoing edges from each vertex
The number of tests is spoiler information?
Partially
The number of tests is not a piece of information which should be hidden...
So, in what way is it a spoiler? It seems more like an unnecessary gotcha. A less generous interepretation is that hiding that detail is punishment for those who do not write a prematurely optimized solution.
7has no connections to anything, let alone "a path to other vertex", how come it forms a strongly connected component?My mistake. We assume that any vertex is reachable from itself. Vertex 7 has no outgoing edges, but each vertex is reachable from itself, so 7 forms a strongly connected component. Now the description is corrected