6日目

データ構造アルゴリズムの復習
白準2606題
ウイルス

from collections import deque
import sys
I = sys.stdin.readline

def breadth_first_search(graph, root):
    queue = deque([root])
    discovered = [root]
    visited = []

    while len(queue) > 0:
        node = queue.popleft()
        visited.append(node)
        undiscovered = set(graph[node]).difference(set(discovered))

        if undiscovered:
            discovered.extend(undiscovered)
            for elem in sorted(undiscovered):
                queue.append(elem)

    return visited


def depth_first_search(graph, root):
    stack = [root]
    discovered = [root]
    visited = []

    while stack:
        node = stack.pop()
        visited.append(node)
        undiscovered = set(graph[node]).difference(set(discovered))

        if undiscovered:
            discovered.extend(undiscovered)
            data = sorted(undiscovered)
            while data:
                a = data.pop()
                stack.append(a)


    return visited


n = int(I())
m = int(I())
graph1 = {}
for i in range(1, n+1):
    graph1[str(i)] = []

for _ in range(m):
    vertex, data = I().split()
    graph1[vertex].append(data)
    graph1[data].append(vertex)

result = breadth_first_search(graph1, '1')
print(len(result) - 1)

結果
特にありませんが、グラフのdirectが基本だと思いますので、データ入力に注意しましょう.
白俊10026号です.
赤緑薬

from collections import deque
import sys
import copy
I = sys.stdin.readline


def breadth_first_search(graph, root):
    queue = deque([root])
    discovered = [root]
    visited = []

    while len(queue) > 0:
        node = queue.popleft()
        visited.append(node)
        undiscovered = set(graph[node]).difference(set(discovered))

        if undiscovered:
            discovered.extend(undiscovered)
            for elem in sorted(undiscovered):
                queue.append(elem)

    return visited


def depth_first_search(graph, root):
    stack = [root]
    discovered = [root]
    visited = []

    while stack:
        node = stack.pop()
        visited.append(node)
        undiscovered = set(graph[node]).difference(set(discovered))

        if undiscovered:
            discovered.extend(undiscovered)
            data = sorted(undiscovered)
            while data:
                a = data.pop()
                stack.append(a)


    return visited


def up(graph, paper, i, j):
    if paper[i][j] == paper[i-1][j]:
        graph[(i, j)].append((i-1,j))


def down(graph, paper, i, j):
    if paper[i][j] == paper[i+1][j]:
        graph[(i, j)].append((i+1,j))


def left(graph, paper, i, j):
    if paper[i][j] == paper[i][j-1]:
        graph[(i, j)].append((i,j-1))


def right(graph, paper, i, j):
    if paper[i][j] == paper[i][j+1]:
        graph[(i, j)].append((i, j+1))


def determine_group_color(graph, paper, n):
    for i in range(n):
        for j in range(n):
            if 1 <= i < n-1 :
                if j == 0:
                    up(graph, paper, i, j)
                    right(graph, paper, i, j)
                    down(graph, paper, i, j)
                elif j == n-1:
                    up(graph, paper, i, j)
                    left(graph, paper, i, j)
                    down(graph, paper, i, j)
                else:
                    up(graph, paper, i, j)
                    right(graph, paper, i, j)
                    down(graph, paper, i, j)
                    left(graph, paper, i, j)
            elif i == 0:
                if j == 0:
                    right(graph, paper, i, j)
                    down(graph, paper, i, j)
                elif j == n-1:
                    left(graph, paper, i, j)
                    down(graph, paper, i, j)
                else:
                    right(graph, paper, i, j)
                    down(graph, paper, i, j)
                    left(graph, paper, i, j)
            else:
                if j == 0:
                    up(graph, paper, i, j)
                    right(graph, paper, i, j)
                elif j == n-1:
                    up(graph, paper, i, j)
                    left(graph, paper, i, j)
                else:
                    up(graph, paper, i, j)
                    right(graph, paper, i, j)
                    left(graph, paper, i, j)


graph = {}
graph_dsb = {}

num = int(I())
li = []
for _ in range(num):
    li.append([color for color in I().rstrip('\n')])

li_dsb = copy.deepcopy(li)
for i in range(num):
    for j in range(num):
        if li_dsb[i][j] == 'G':
            li_dsb[i][j] = 'R'

for i in range(num):
    for j in range(num):
        graph[(i,j)] = []
for i in range(num):
    for j in range(num):
        graph_dsb[(i,j)] = []


determine_group_color(graph, li, num)
determine_group_color(graph_dsb, li_dsb, num)

li = []
li_dsb = []
cnt = 0
cnt_dsb = 0
for i in range(num):
    for j in range(num):
        if (i, j) not in li:
            li.extend(breadth_first_search(graph, (i, j)))
            cnt += 1

for i in range(num):
    for j in range(num):
        if (i, j) not in li_dsb:
            li_dsb.extend(breadth_first_search(graph_dsb, (i, j)))
            cnt_dsb += 1
print(cnt, cnt_dsb)

結果
処理速度が遅く、コードが混乱している.解題アルゴリズムでは,人間の解題方式を直感的に受け入れ,加工を経ずに体現し,専門性がない.今Pythonの文法を熟知するため、資料の構造を熟知して、後で解釈することを決定します.
接触したエラー
TypeError : unhashable type: 'set'
->dictionaryのkey dataに可変値が含まれている場合に発生します.