Re: [algogeeks] Re: Find the number of islands/connected components
got the islands...but first we scan each element then also dfs for them if
all are 1..then how it can be o(row*col)...plz explain me complexity ofr
this
On Fri, Apr 26, 2013 at 2:07 PM, atul anand wrote:
> {*1*,* 1*, 0, 0, 0},
> {0, *1*, 0, 0, *1*
> },
> {*1*, 0, 0, *1*, *1*},
> {0, 0, 0, 0, 0},
> {*1*, 0, *1*, 0, *1*}
>
> above different set of color represent different island.Simple DFS is used to
> find all the island
>
>
>
> On Fri, Apr 26, 2013 at 3:11 AM, Don wrote:
>
>> The complexity is still O(ROWS*COLS) because each location in the
>> matrix will be visited once by the loop and once by DFS. Once a
>> location has been visited by DFS, it is marked as visited and can't be
>> visited again.
>> Don
>>
>> On Apr 25, 5:11 pm, rahul sharma wrote:
>> > What will be complexity if all elements in matrix are 1..
>> >
>> > when first dfs will call then all matrix will be scanned setting each
>> > element to visited...
>> > then again loop contiues to scan all the elements..plz explain
>> >
>> > On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma > >wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > {*1*,* 1*, 0, 0, 0},
>> > > {0, *1*, 0, 0, *1*},
>> > > {*1*, 0, 0, *1*, *1*},
>> > > {0, 0, 0, 0, 0},
>> > > {*1*, 0, *1*, 0, *1*}
>> >
>> > > Can anybody eplain how there are 5 islands in above matrix..thnx in
>> advance
>> >
>> > > source:-http://www.geeksforgeeks.org/find-number-of-islands/
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Find the number of islands/connected components
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
above different set of color represent different island.Simple DFS is
used to find all the island
On Fri, Apr 26, 2013 at 3:11 AM, Don wrote:
> The complexity is still O(ROWS*COLS) because each location in the
> matrix will be visited once by the loop and once by DFS. Once a
> location has been visited by DFS, it is marked as visited and can't be
> visited again.
> Don
>
> On Apr 25, 5:11 pm, rahul sharma wrote:
> > What will be complexity if all elements in matrix are 1..
> >
> > when first dfs will call then all matrix will be scanned setting each
> > element to visited...
> > then again loop contiues to scan all the elements..plz explain
> >
> > On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma >wrote:
> >
> >
> >
> >
> >
> >
> >
> > > {*1*,* 1*, 0, 0, 0},
> > > {0, *1*, 0, 0, *1*},
> > > {*1*, 0, 0, *1*, *1*},
> > > {0, 0, 0, 0, 0},
> > > {*1*, 0, *1*, 0, *1*}
> >
> > > Can anybody eplain how there are 5 islands in above matrix..thnx in
> advance
> >
> > > source:-http://www.geeksforgeeks.org/find-number-of-islands/
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Find the number of islands/connected components
islands are five as for each cell we assume all surrounding positions to be
connected... so if coordinates are (x,y) then it is connected to (x+1, y),
(x-1, y), (x+1, y+1), (x-1, y+1), (x+1, y-1), (x-1, y-1), (x, y-1), (x, y+1)
On Thu, Apr 11, 2013 at 9:35 AM, rahul sharma wrote:
> I didnt get..plz explain more...thnx
>
>
> On Thursday, April 11, 2013, Don wrote:
> > Reformatting to make it easier to see:
> >
> > 11000
> > 01001
> > 10011
> > 0
> > 10101
> >
> > In this case an "island" is any set of "1's" which are connected
> > vertically, horizontally, or diagonally.
> > So the five islands are
> >
> > 11000
> > 01002
> > 10022
> > 0
> > 30405
> >
> > Don
> >
> > On Apr 10, 4:34 pm, rahul sharma wrote:
> >> {*1*,* 1*, 0, 0, 0},
> >> {0, *1*, 0, 0, *1*},
> >> {*1*, 0, 0, *1*, *1*},
> >> {0, 0, 0, 0, 0},
> >> {*1*, 0, *1*, 0, *1*}
> >>
> >> Can anybody eplain how there are 5 islands in above matrix..thnx in
> advance
> >>
> >> source:-http://www.geeksforgeeks.org/find-number-of-islands/
> >
> > --
> > You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> > To unsubscribe from this group and stop receiving emails from it, send
> an email to algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit https://groups.google.com/groups/opt_out.
> >
> >
> >
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
Regards,
Arpit Sood
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
