1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from enum import Enum

class GraphType(Enum):
    DOUGHNUT = 1
    STICK = 2
    FIGURE_OF_EIGHT = 3


def get_graph_type(edge_frequency, start_edge):
    queue = [start_edge]
    linked_edges = set()
    linked_count = -1
    while queue:
        from_edge = queue.pop()
        linked_edges.add(from_edge)
        linked_count += 1
        if from_edge in edge_frequency.keys():
            queue.extend(edge_frequency.get(from_edge))
            edge_frequency.pop(from_edge)
    edge_count = len(linked_edges)
    if edge_count == linked_count:
        return GraphType.DOUGHNUT.value
    if edge_count == linked_count + 1:
        return GraphType.STICK.value
    if edge_count == linked_count - 1:
        return GraphType.FIGURE_OF_EIGHT.value
    return 0

def solution(edges):
    answer = [0, 0, 0, 0]
    edge_frequency = dict()
    for from_edge, to_edge in edges:
        edge_frequency.setdefault(from_edge, []).append(to_edge)
    answer[0] = max(edge_frequency.items(), key=lambda x: len(x[1]))[0]
    for start_edge in edge_frequency.pop(answer[0]):
        graph_type = get_graph_type(edge_frequency, start_edge)
        answer[graph_type] += 1
    return answer