Styjun

Is it right to use the ideas of non-winning designers in a design contest?

When was "Cable Select" introduced for IDE devices?

How do you say "to hell with everything" in French?

How do German speakers decide what should be on the left side of the verb?

When did computers stop checking memory on boot?

How to finish my PhD?

Do aarakocra have arms as well as wings?

Project Euler problem #112

Owner keeps cutting corners and poaching workers for his other company

Bacteria vats to generate edible biomass, require intermediary species?

Why is it that I have to play this note on the piano as A sharp?

The meaning of "offing" in "an agreement in the offing"

Why does PAUSE key have a long make code and no break code?

Extra arrow heads appearing tikz

Why are some hotels asking you to book through Booking.com instead of matching the price at the front desk?

Template default argument loses its reference type

More than three domains hosted on the same IP address

If every star in the universe except the Sun were destroyed, would we die?

Leaving the USA for 10 yrs when you have asylum

How should Thaumaturgy's "three times as loud as normal" be interpreted?

How strong is aircraft-grade spruce?

How to plot two curves with the same area under?

When does order matter in probability?

Examples where "thin + thin = nice and thick"

How to find area of connected islands (graph theory python)

How can I represent an 'Enum' in Python?Python Graph LibraryHow do I use raw_input in Python 3Connectivity of a GraphWhy DFS and not BFS for finding cycle in graphsHow to install pip with Python 3?Graph Theory Depth First Searchhow to find the original directed graph?Finding all possible paths in a fully connected graph in pythonFinding Connectivity in a Graph

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

0

Hi I'm referring to the Graph Theory problem of finding connected islands.
https://www.geeksforgeeks.org/find-the-number-of-islands-set-2-using-disjoint-set/
This helps to find the number of connected islands.

I have a related problem: Find the area of the largest islands (1) including the water(0) that it surrounds. The code for finding connected islands is below. But I don't know how to go about writing an algorithm for finding area...

def numIslands(graph):

 row = len(graph)
 col = len(graph[0])
 count += 1

 for i in range(row):
 for j in range(col):
 if graph[i][j] == 1:
 dfs(graph, row, col, i, j)
 count += 1
 return count

def dfs(graph, row, col, x, y):
 if graph[x][y] == 0:
 return

 graph[x][y] = 0

 if x != 0:
 dfs(graph, row, col, x-1, y)

 if x != rows - 1:
 dfs(graph, row, col, x+1, y)

 if y != 0:
 dfs(graph, row, col, x, y-1)

 if y != col-1:
 dfs(graph, row, col, x, y+1)

The sample inputs and outputs are as below:

1111 
0101
11110

Area: 10

101
010
101

Area: 1

11111
10011 
11111

Area: 15

1111111
1000001
1011101
1000001
1111111

Area 35

1111111
1000001
1011100
1000001
1111111

Area 19

Any suggestions on how to go about would be appreciated!

python-3.x graph depth-first-search breadth-first-search

share|improve this question

edited Mar 28 at 8:26

spidermarn

asked Mar 28 at 6:27

spidermarnspidermarn

14811 silver badge88 bronze badges

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Each 1 or 0 (a node) represents a unit of area (be it 1 sq. mm or 1 sq. km or what ever, so the island area equals to the total number of 1 + total number of 0 it surrounds.
  
  – c0der
  Mar 30 at 13:39
  

  
  
  
  

add a comment | 

0

Hi I'm referring to the Graph Theory problem of finding connected islands.
https://www.geeksforgeeks.org/find-the-number-of-islands-set-2-using-disjoint-set/
This helps to find the number of connected islands.

I have a related problem: Find the area of the largest islands (1) including the water(0) that it surrounds. The code for finding connected islands is below. But I don't know how to go about writing an algorithm for finding area...

def numIslands(graph):

 row = len(graph)
 col = len(graph[0])
 count += 1

 for i in range(row):
 for j in range(col):
 if graph[i][j] == 1:
 dfs(graph, row, col, i, j)
 count += 1
 return count

def dfs(graph, row, col, x, y):
 if graph[x][y] == 0:
 return

 graph[x][y] = 0

 if x != 0:
 dfs(graph, row, col, x-1, y)

 if x != rows - 1:
 dfs(graph, row, col, x+1, y)

 if y != 0:
 dfs(graph, row, col, x, y-1)

 if y != col-1:
 dfs(graph, row, col, x, y+1)

The sample inputs and outputs are as below:

1111 
0101
11110

Area: 10

101
010
101

Area: 1

11111
10011 
11111

Area: 15

1111111
1000001
1011101
1000001
1111111

Area 35

1111111
1000001
1011100
1000001
1111111

Area 19

Any suggestions on how to go about would be appreciated!

python-3.x graph depth-first-search breadth-first-search

share|improve this question

edited Mar 28 at 8:26

spidermarn

asked Mar 28 at 6:27

spidermarnspidermarn

14811 silver badge88 bronze badges

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Each 1 or 0 (a node) represents a unit of area (be it 1 sq. mm or 1 sq. km or what ever, so the island area equals to the total number of 1 + total number of 0 it surrounds.
  
  – c0der
  Mar 30 at 13:39
  

  
  
  
  

add a comment | 

Hi I'm referring to the Graph Theory problem of finding connected islands.
https://www.geeksforgeeks.org/find-the-number-of-islands-set-2-using-disjoint-set/
This helps to find the number of connected islands.

I have a related problem: Find the area of the largest islands (1) including the water(0) that it surrounds. The code for finding connected islands is below. But I don't know how to go about writing an algorithm for finding area...

def numIslands(graph):

 row = len(graph)
 col = len(graph[0])
 count += 1

 for i in range(row):
 for j in range(col):
 if graph[i][j] == 1:
 dfs(graph, row, col, i, j)
 count += 1
 return count

def dfs(graph, row, col, x, y):
 if graph[x][y] == 0:
 return

 graph[x][y] = 0

 if x != 0:
 dfs(graph, row, col, x-1, y)

 if x != rows - 1:
 dfs(graph, row, col, x+1, y)

 if y != 0:
 dfs(graph, row, col, x, y-1)

 if y != col-1:
 dfs(graph, row, col, x, y+1)

The sample inputs and outputs are as below:

1111 
0101
11110

Area: 10

101
010
101

Area: 1

11111
10011 
11111

Area: 15

1111111
1000001
1011101
1000001
1111111

Area 35

1111111
1000001
1011100
1000001
1111111

Area 19

Any suggestions on how to go about would be appreciated!

python-3.x graph depth-first-search breadth-first-search

share|improve this question

edited Mar 28 at 8:26

spidermarn

asked Mar 28 at 6:27

spidermarnspidermarn

14811 silver badge88 bronze badges

def numIslands(graph):

 row = len(graph)
 col = len(graph[0])
 count += 1

 for i in range(row):
 for j in range(col):
 if graph[i][j] == 1:
 dfs(graph, row, col, i, j)
 count += 1
 return count

def dfs(graph, row, col, x, y):
 if graph[x][y] == 0:
 return

 graph[x][y] = 0

 if x != 0:
 dfs(graph, row, col, x-1, y)

 if x != rows - 1:
 dfs(graph, row, col, x+1, y)

 if y != 0:
 dfs(graph, row, col, x, y-1)

 if y != col-1:
 dfs(graph, row, col, x, y+1)

1111 
0101
11110

Area: 10

101
010
101

Area: 1

11111
10011 
11111

Area: 15

1111111
1000001
1011101
1000001
1111111

Area 35

1111111
1000001
1011100
1000001
1111111

Area 19

share|improve this question

edited Mar 28 at 8:26

spidermarn

asked Mar 28 at 6:27

spidermarnspidermarn

14811 silver badge88 bronze badges

share|improve this question

edited Mar 28 at 8:26

spidermarn

asked Mar 28 at 6:27

spidermarnspidermarn

14811 silver badge88 bronze badges

asked Mar 28 at 6:27

spidermarnspidermarn

14811 silver badge88 bronze badges

asked Mar 28 at 6:27

spidermarnspidermarn

14811 silver badge88 bronze badges