Ask Lemmy
A Fediverse community for open-ended, thought provoking questions
Please don't post about US Politics. If you need to do this, try !politicaldiscussion@lemmy.world
Rules: (interactive)
1) Be nice and; have fun
Doxxing, trolling, sealioning, racism, and toxicity are not welcomed in AskLemmy. Remember what your mother said: if you can't say something nice, don't say anything at all. In addition, the site-wide Lemmy.world terms of service also apply here. Please familiarize yourself with them
2) All posts must end with a '?'
This is sort of like Jeopardy. Please phrase all post titles in the form of a proper question ending with ?
3) No spam
Please do not flood the community with nonsense. Actual suspected spammers will be banned on site. No astroturfing.
4) NSFW is okay, within reason
Just remember to tag posts with either a content warning or a [NSFW] tag. Overtly sexual posts are not allowed, please direct them to either !asklemmyafterdark@lemmy.world or !asklemmynsfw@lemmynsfw.com.
NSFW comments should be restricted to posts tagged [NSFW].
5) This is not a support community.
It is not a place for 'how do I?', type questions.
If you have any questions regarding the site itself or would like to report a community, please direct them to Lemmy.world Support or email info@lemmy.world. For other questions check our partnered communities list, or use the search function.
Reminder: The terms of service apply here too.
Partnered Communities:
Logo design credit goes to: tubbadu
view the rest of the comments
To kick us off, mine from this week that I wrote down in another thread. In 60 minutes take an adjacency matrix as an input, good old
int[][], and return all of the disjointed groups, and their group sizes in descending order.I'd like to phone a friend
No you just start by marking all nodes as unvisited and perform a search from a random starting node. you store the current bfs set of vertices in a sorted datastructure. Repeat until there are no more unvisited nodes.
Bingo. For each node if it's 0 continue if it's 1 then bfs to get everything. Store that group temporarily and mark which nodes you've seen. For the remaining nodes check if they are 1 and you have not seen it and continue. O(n log n) I believe, since you still iterate over everything and check
Thanks friend!
I think this is basically testing:
Correct! I don't like it, but gotta play the game if you want to make the cash