DFS variation
Hello,
https://www.geeksforgeeks.org/find-number-of-islands/
This is the link to the classic island problem where number of islands have to be found.
My doubt is on a variation of this problem, I have listed my approach here as well.
Suppose the islands are divided into types from 1 to 10^6, and we have to find maximum number of islands such that they belong to one of two categories (eg 1 and 2, 1 and 3, 5 and 6 etc), and they are all connected to each other (ie two different portions are not acceptable.)
My approach for this-
First I made a array of all types.
Then I run two loops, one inside another ( loop2 beginning from loop1), and run dfs from every unvisited node. I made a global variable and incremented it on every encounter with a island of type 1 or 2. then stored the max of this.
I then mark all visited nodes as false and start again from new island category pairs.
Basically a very naive approach.
This fails for bigger numbers, any suggestions on how it can be optimised are welcome.
If I have failed to explain the question or my approach, please mention it, I'll try again.
Cheers.
https://www.geeksforgeeks.org/find-number-of-islands/
This is the link to the classic island problem where number of islands have to be found.
My doubt is on a variation of this problem, I have listed my approach here as well.
Suppose the islands are divided into types from 1 to 10^6, and we have to find maximum number of islands such that they belong to one of two categories (eg 1 and 2, 1 and 3, 5 and 6 etc), and they are all connected to each other (ie two different portions are not acceptable.)
My approach for this-
First I made a array of all types.
Then I run two loops, one inside another ( loop2 beginning from loop1), and run dfs from every unvisited node. I made a global variable and incremented it on every encounter with a island of type 1 or 2. then stored the max of this.
I then mark all visited nodes as false and start again from new island category pairs.
Basically a very naive approach.
This fails for bigger numbers, any suggestions on how it can be optimised are welcome.
If I have failed to explain the question or my approach, please mention it, I'll try again.
Cheers.
Topic archived. No new replies allowed.