バックアップの問題解決11724接続要素数

5959 ワード
テキストリンク
boj 11724:接続要素数
質問アドレス:https://www.acmicpc.net/problem/11724
難易度:silver 2
1.問題の説明
  • の無方向図が与えられると、接続要素の個数
    • が求める.
    2.問題を解決する考え.
  • 接続要素とは何か、接続されていない部分図の個数を理解しますか?と理解する.
  • そうであれば、bfsを使用して特定の場所にアクセスし、
  • に接続されているすべての場所を探索します!
    • 3.問題の処理方法
  • bfsを用いて探索を開始し,探索の部分をアクセスに置く.
    • for文を使用して
  • ノードにアクセスしていない場合、bfsが実行され、アクセス処理が行われる.
    • 4.特別注意事項
  • で最初にタイムアウトが発生しました.
  • どう考えてもこれ以上きつくはならず、恥ずかしさに陥って検索してみると
    • Sysは
  • input()に代わります.stdin.readlineで解決しました.
  • 以降はSYstdin.私はreadline、
    • しか書いていません.
    5.コード実装
    from collections import deque
import sys
input = sys.stdin.readline
N, E = map(int, input().split())
graph = [[] for _ in range(N+1)]
for i in range(E):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

visited = set()
def bfs(graph, start):
    queue = deque([start])
    while queue:
        curNode = queue.popleft()
        for node in graph[curNode]:
            if node not in visited:
                queue.append(node)
                visited.add(node)

cnt = 0
for i in range(1,N+1):
    if i not in visited:
        bfs(graph, i)
        visited.add(i)
        cnt += 1

print(cnt)
    Android Xutils dbuils注記
    GATSBY - 5をグラフ化する方法- Gatsbyがデータを食べる方法