Examining the slide

Consider every black cell as a vertex of a graph. For each one, look around and create an edge for each neighbour black cell.

The problem is now to compute the size of each connected part of the graph. This can be done by assigning value 1 to each black cell and remove them one after another: e.g. if A is connected to B, C and D:

• add value of A to B;
• create edges from B to C and D if they don't already exist;
• erase edges A-B, A-C and A-D;
• assign value of 0 to A

When a vertex has no more edges, its value gives the size of its connected part.

# Python code
vertices = [ [  1, 1, 0, 1, 1, 0, ... ],
             [  0, 0, 1, 0, 0, 1, ... ],
                 ...
             [  0, 0, 1, 0, 0, 0, ... ],
             [  1, 0, 0, 0, 0, 0, ... ]
           ]

N=len(vertices)

# Stage 1 : compute edges
edges = []
for i in xrange(N):
    edges += [ [] ]
    for j in xrange(N):
        edges[i] += [ [] ]
        if vertices[i][j] == 0:
            continue
        # look only forward, it's enough
        for d in [[0,1],[1,-1],[1,0],[1,1]]:
            a = i + d[0]
            b = j + d[1]
            if a>=0 and b>=0 and a<N and b<N:
                if vertices[a][b] == 1:
                    edges[i][j] += [ (a,b) ]


# Stage 2 : remove black cells when they're connected to another one
for i in xrange(N):
    for j in xrange(N):
        if vertices[i][j] == 0:
            # not a black cell
            continue
        if len(edges[i][j]) == 0:
            # no more to do, its number is the size of its connected part
            continue

        # new cell to which everything is transfered
        newcell = edges[i][j][0]
        # transfer value of the current cell
        vertices[newcell[0]][newcell[1]] += vertices[i][j]
        vertices[i][j] = 0
        # remove edge from new one to current one
        edges[newcell[0]][newcell[1]] = [k for k in edges[newcell[0]][newcell[1]] if k<>(i,j)]
        # transfer edges to new vertex
        for e in edges[i][j]:
            # add edges only if not new cell itself, and if not already there
            if e == newcell:
                continue
            if e not in edges[newcell[0]][newcell[1]]:
               edges[newcell[0]][newcell[1]] += [e]
               edges[e[0]][e[1]] += [ newcell ]
            # erase edge information also on e's list
            edges[e[0]][e[1]] = [k for k in edges[e[0]][e[1]] if k<>(i,j)]
        edges[i][j] = []

# Stage 3: find max size
print max([max(i) for i in vertices])