徒然weed

アウトプットの場

ゆる〜くpythonの練習「連結成分編」

f:id:shintaro-football7:20191022195746p:plain

今回は連結成分についてです。SNSの友達関係を想定しているみたいです。

問題はこちら。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_D

有向グラフではないため[3 5]という入力があったらqueue[3]に5をプッシュするのはいいとしてqueue[5]にも3をプッシュしなければなりません。僕はこれで最初ミスってました...

from collections import deque

n,m = map(int,input().split())

V =[deque([]) for _ in range(n)]
color = [0 for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)

friend = 1

def dfs(u,f):
    global color
    color[u] = f
    stack = []
    stack.append(u)
    while len(stack) != 0:
        now = stack[-1]
        if len(V[now]) != 0:
            nb = V[now].popleft()
            if color[nb] == 0:
                stack.append(nb)
                color[nb] = f
        else :
            stack.pop()

for i in range(n):
    if color[i]==0:
        dfs(i,friend)
        friend += 1

q = int(input())
for _ in range(q):
    a,b = map(int,input().split())
    if color[a] == color[b]:
        print("yes")
    else:
        print("no")

 

本日のおまけ