結果

問題 No.1254 補強への架け橋
ユーザー titia
提出日時 2020-10-10 01:01:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 388 ms / 2,000 ms
コード長 968 bytes
コンパイル時間 530 ms
コンパイル使用メモリ 81,848 KB
実行使用メモリ 145,108 KB
最終ジャッジ日時 2024-07-20 15:07:11
合計ジャッジ時間 20,936 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます

ソースコード

diff # 

N=int(input())
EDGE=[tuple(map(int,input().split())) for i in range(N)]

E=[[] for i in range(N+1)]

for x,y in EDGE:
    E[x].append(y)
    E[y].append(x)

Q=[(1,N+5)]
USE=[0]*(N+1)
FR=[-1]*(N+1)
USE[1]=1

while Q:
    x,fr=Q.pop()
    ANS=-1

    for to in E[x]:
        if fr==to:
            continue
        if USE[to]==0:
            USE[to]=1
            FR[to]=x
            Q.append((to,x))
        else:
            ANS=to
            NOW=x
            break
    if ANS!=-1:
        break

LIST0=[]
LIST1=[]

while NOW!=1:
    LIST0.append(NOW)
    NOW=FR[NOW]

while ANS!=1:
    LIST1.append(ANS)
    ANS=FR[ANS]

LIST0.append(1)
LIST1.append(1)

while LIST0[-1]==LIST1[-1]:
    x=LIST0.pop()
    y=LIST1.pop()

LIST=[x]+LIST0[::-1]+LIST1

SET=set()
for i in range(len(LIST)):
    x=LIST[i-1]
    y=LIST[i]
    SET.add((x,y))
    SET.add((y,x))

ALIST=[]
for i in range(N):
    if EDGE[i] in SET:
        ALIST.append(i+1)

print(len(ALIST))
print(*ALIST)
0