[BOJ]白俊4083号樹(Python)

質問する

グラフは頂点と幹線で構成されています.2つの頂点の間にパスがある場合、2つの頂点は接続されていると言われています.接続要素は、すべての頂点が相互に接続されている頂点の一部の集合です.グラフィックは、1つ以上の接続要素から構成されます.
ツリーはループのない接続要素です.木にはいろいろな性質がある.たとえば、ツリーにはn個の頂点があり、n-1本の幹線があります.また、パスは、任意の2つの頂点に対して一意です.
グラフィックが指定されている場合は、ツリーの数を計算するプログラムを作成します.

入力

入力は、複数の試験例から構成される.

各試験例の第1行は、n≦500およびm≦n(n−1)/2を満たす頂点個数nおよび幹線個数mを与える.

次のm行には、幹線を表す整数が2つあります.

のような幹線は何度も与えられません.

頂点は1番からn番までです.

入力の最後の行は2つのゼロを与える.

しゅつりょく

指定されたグラフィックにツリーがない場合は、

と入力します.乙,

個なら「There is one tree」です.乙,

T個(T>1)すると、「Aの森のTツリー.テスト用例番号とともに出力します.

例

入力

6 3
1 2
2 3
3 4
6 5
1 2
2 3
3 4
4 5
5 6
6 6
1 2
2 3
1 3
4 5
5 6
6 4
0 0

しゅつりょく

Case 1: A forest of 3 trees.
Case 2: There is one tree.
Case 3: No trees.

に答える

from collections import deque

def check(num):					# num으로 받은 노드가 트리인지 확인하는 함수
    visited[num] = True				# 이제 방문함.
    queue = deque([num])			# BFS를 위한 queue

    while queue:
        node = queue.popleft()			# 노드 가져옴
        for n_node in trees[node]:              # bfs. 해당 노드에 연결된 노드들 차례로 가져옴.
            if trees[node][n_node] == 0:        # 엣지 체크 (0: 체크 안함, 1: 체크함)
                if not visited[n_node]:         # 해당 노드에 처음 방문
                    visited[n_node] = True
                    queue.append(n_node)        # 대기열에 다음 노드 추가
                    trees[node][n_node] = 1	# 엣지 체크
                    trees[n_node][node] = 1	# 엣지 체크
                else:
                    return False                # 헤당 노드에 방문한 적이 있으므로 이는 트리가 아닌 그래프
    return True

test = 0
while True:
    test += 1
    N, M = map(int, input().split())
    if N == 0 and M == 0:			# 0 0 입력시 종료
        break
    edges = [list(map(int, input().split())) for _ in range(M)]
    visited = [False] * (N + 1)			# 방문여부 확인용
    trees = [{} for _ in range(N+1)]		# 노드 별 연결된 엣지 모음
    for e in edges:
        trees[e[0]][e[1]] = 0           	# 엣지 체크. 0: 체크X / 1: 체크 O
        trees[e[1]][e[0]] = 0

    cnt = 0					# 트리 갯수
    for num in range(1, N + 1):			# 모든 노드 확인
        if not visited[num]:			# 해당 노드 방문 안한 경우
            if check(num):			# 트리인지 체크함
                cnt += 1

    # 출력
    print("Case {}: ".format(test), end="")
    if cnt == 0:
        print("No trees.")
    elif cnt == 1:
        print("There is one tree.")
    else:
        print("A forest of {} trees.".format(cnt))

python 3でコミットするとタイムアウトし、python 3でコミットすると良いです.
python 3の使い方を学ぶ必要があります.