largest_island.py

from typing import List, Tuple, Mapping, Set
from collections import defaultdict

Graph = Mapping[str, Set[str]]
Connection = Tuple[str, str]


def createGraph(connections: List[Connection]) -> Graph:
    graph: Graph = defaultdict(set)
    for a, b in connections:
        graph[a].add(b)
        graph[b].add(a)
    return graph


def getIsland(graph: Graph, startNode: str) -> Set[str]:
    island = set()
    frontier = set(startNode)
    while frontier:
        currentNode = frontier.pop()
        island.add(currentNode)
        for connectedNode in graph[currentNode]:
            if connectedNode not in island:
                frontier.add(connectedNode)
    return island


def getLargestIslandSize(graph: Graph) -> int:
    startNodes = set(graph.keys())
    largestIslandSize = 0
    while startNodes and len(startNodes) > largestIslandSize:
        startNode = startNodes.pop()
        island = getIsland(graph, startNode)
        for node in island:
            startNodes.discard(node)
        largestIslandSize = max(largestIslandSize, len(island))
    return largestIslandSize


def solution(connections: List[Connection]):
    graph = createGraph(connections)
    print(dict(graph))
    return getLargestIslandSize(graph)


def main():
    example = [('A', 'B'), ('D', 'C'), ('E', 'F'), ('B', 'C')]
    print(solution(example))


if __name__ == '__main__':
    main()