[SWEA]#5643キー順

質問リンク

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AWXQsLWKd5cDFAUo&categoryId=AWXQsLWKd5cDFAUo&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=PYTHON&select-1=4&pageSize=10&pageIndex=3

n/a.計画

単純に一方向に隣接する頂点については,アクセスの有無だけでなく,すべての点に接続されているかどうかも確認する.最初はすべての幹線の方向をひっくり返せばいいと思っていたのですが、入るのも入るのも確認しなければならないようなので、いっそ隣同士のリストを2つ作りたいと思いました.

コード#コード#

def count_visited(arr, start):
    visited = [0] * (N + 1)
    stack = [start]
    while stack:
        now = stack.pop()
        for nxt in arr[now]:
            if not visited[nxt]:
                visited[nxt] = 1
                stack.append(nxt)

    return visited.count(1)


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    M = int(input())
    cnt = 0
    adj_out = [[] for _ in range(N + 1)]
    adj_in = [[] for _ in range(N + 1)]

    for _ in range(M):
        a, b = map(int, input().split())
        adj_out[a].append(b)
        adj_in[b].append(a)

    for student in range(1, N + 1):
        if count_visited(adj_out, student) + count_visited(adj_in, student) == N - 1:
            cnt += 1

    print('#{} {}'.format(tc, cnt))

解答方法

また、隣接する頂点をカウントできる関数を記述し、すべての頂点に対してin&out隣接リストの戻り値をチェックし、その値が頂点の個数に等しい場合は+1で解く.