 # Untitled

Aug 5th, 2021
639
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #%%
2. class Graph:
3.
4.     def __init__(self, row, col, g):
5.         self.ROW = row
6.         self.COL = col
7.         self.graph = g
8.
9.     def isSafe(self, i, j, visited):
10.         return (
11.             i >= 0 and i < self.ROW
12.             and j >= 0 and j < self.COL
13.             and not visited[i][j]
14.             and self.graph[i][j]
15.         )
16.
17.
18.     # A utility function to do DFS for a 2D
19.     # boolean matrix. It only considers
20.     # the 8 neighbours as adjacent vertices
21.     def DFS(self, i, j, visited):
22.
23.         # These arrays are used to get row and
24.         # column numbers of 8 neighbours
25.         # of a given cell
26.         rowNbr = [-1, 0, 0,  1]
27.         colNbr = [0, -1, 1, 0]
28.
29.         # Mark this cell as visited
30.         visited[i][j] = True
31.
32.         # Recur for all connected neighbours
33.         count = 1
34.         for k in range(4):
35.             if self.isSafe(i + rowNbr[k], j + colNbr[k], visited):
36.                 count += self.DFS(i + rowNbr[k], j + colNbr[k], visited)
37.
38.         return count
39.
40.     def diagCheck(self, i, j):
41.         rowNbr = [-1, 1, -1,  1]
42.         colNbr = [1, -1, -1, 1]
43.
44.         ans = True
45.         for k in range(4):
46.             if i >= 0 and i < self.ROW and j >= 0 and j < self.COL:
47.                 ans = ans and self.graph[i + rowNbr[k]][j + colNbr[k]] == 0
48.         return ans
49.
50.
51.     # The main function that returns
52.     # count of islands in a given boolean
53.     # 2D matrix
54.     def countIslands(self):
55.         # Make a bool array to mark visited cells.
56.         # Initially all cells are unvisited
57.         visited = [[False for j in range(self.COL)]for i in range(self.ROW)]
58.
59.         # Initialize count as 0 and traverse
60.         # through the all cells of
61.         # given matrix
62.         count = 0
63.         for i in range(self.ROW):
64.             for j in range(self.COL):
65.                 # If a cell with value 1 is not visited yet,
66.                 # then new island found
67.                 if visited[i][j] == False and self.graph[i][j] == 1:
68.                     # Visit all cells in this island
69.                     # and increment island count
70.                     t = self.DFS(i, j, visited)
71.                     if t > 1:
72.                         count += 1
73.                     else:
74.                         if self.diagCheck(i, j):
75.                             count += 1
76.
77.         return count
78.
79. #%%
80. # graph = [[1, 1, 0, 0, 0],
81. #         [0, 1, 0, 0, 1],
82. #         [1, 0, 0, 1, 1],
83. #         [0, 0, 0, 0, 0],
84. #         [1, 0, 1, 0, 1]]
85.
86. # graph = [
87. #     [1, 0, 1, 1],
88. #     [0, 0, 1, 0],
89. #     [1, 0, 1, 1],
90. #     [1, 0, 1, 0]
91. # ]
92.
93. graph = [
94.     [1, 0, 0, 0, 0, 1, 1],
95.     [0, 1, 0, 0, 0, 1, 0],
96.     [0, 0, 1, 0, 0, 1, 1],
97.     [1, 0, 0, 1, 0, 1, 1],
98.     [1, 0, 0, 0, 0, 0, 0]
99. ]
100.
101. #%%
102. row = len(graph)
103. col = len(graph)
104.
105. g = Graph(row, col, graph)
106.
107. print("Number of islands is:")
108. print(g.countIslands())
109. # %%
110.
RAW Paste Data