白準2606ウイルス

白準2606ウイルス

間違った答え.
com dict:接続関係を表すディック声明
≪アクセス｜Access｜ldap≫:アクセスしたノードの配列
mustgo:アクセスするノード配列
基本プロセス
:
アクセス順にかかわらず回数だけ要求すれば良いので、コードを作るのは簡単です.
1)1から.
2)1に接続したノードをすべてmustgo配列に入れる.
3)mustgoがなくなるまでドアを回します.
4)mustgoからノードをポップアップしてアクセスする.
5)結果値に1を加算します.
6)アクセスしたノードをアクセスに入れ,そのノードに関連付けられたすべてのノードをmustgoに入れる.上にも述べましたが、アクセス順は関係ありません.popもpopleftも自由です
(ここにmustgoを入れるノードはアクセス中に存在しない)
最初は双方向とは思いませんでしたが、左の値が1の場合だけ考えました.
しかし、最初に提出した答えは間違っているので、反例を探すときは双方向を考えなければなりません.
1 2
2 3
3 4
5 6
6 7
7 8
8 1
例えば、このような場合、1に接続された8は認識されない.
双方向入力に変更し、重複を排除してコミットします.
また間違えた.
どこが間違っているのか分からず、半日探して、入力例を加えると、別の値が得られます.
従来,新しいノードをmustgoに入れる際にアクセスするだけでなく,mustgoにも重複するノードがあるべきではなかった.
何度も間違っていましたが、自分がこの解答を思いついたことを嬉しく思います.

import sys

x = int(sys.stdin.readline())
y = int(sys.stdin.readline())

com_dict = {}
visited = []
mustgo = []
result = 0

for i in range(y) :
    a,b = map(int,sys.stdin.readline().rstrip().split())
    if a in com_dict :
        if b not in com_dict[a]:
            com_dict[a].append(b)
    else :
        com_dict[a] = [b]

    if b in com_dict :
        if a not in com_dict[b]:
            com_dict[b].append(a)
    else :
        com_dict[b] = [a]


if 1 not in com_dict :
    print(0)
    quit()

for i in range(len(com_dict[1])) :
    mustgo.append(com_dict[1].pop())

visited.append(1)
del com_dict[1]

while len(mustgo) > 0 :
    nowAt = mustgo.pop()
    visited.append(nowAt)
    result += 1
    if nowAt in com_dict :
        for i in range(len(com_dict[nowAt])) :
            inNowAt = com_dict[nowAt].pop()
            if inNowAt not in visited and inNowAt not in mustgo:
                mustgo.append(inNowAt)

print(result)