ALDS1_11_D: Connected Components

頂点どうしが連結しているかどうかを判定する問題

ここまで、入力の形式が連結リストになっていたけれども
この問題では連結している頂点のペアの並びで与えられている
これだと隣接行列の形に読み込むほうが少し楽かな？
重複考えなくていいし
ここまで隣接行列でやってきた流れはそういうことなのか

重複しても別に問題ないと思うけど
隣接リストをSetで覚えるという方法もあるね
でもたまには隣接行列でやってみよう

qが10000もあるということは、毎回グラフをたどったりしてるとTLEだな
最初に塗り分けてしまうか

やったー0オリジンだ―

def read_friends():
    n, m = [int(x) for x in input().split()]
    adj_mat = [[False] * n for _ in range(n)]

    for _ in range(m):
        s, t = [int(x) for x in input().split()]
        adj_mat[s][t] = True
        adj_mat[t][s] = True

    return n, adj_mat

def divide_group(n, adj_mat):
    group = [None] * n

    def visit(k, g):
        group[k] = g
        for t, connected in enumerate(adj_mat[k]):
            if connected and group[t] is None:
                visit(t, g)

    for k in range(n):
        if group[k] is None:
            visit(k, k)

    return group

def answer_queries(group):
    q = int(input())

    for _ in range(q):
        s, t = [int(x) for x in input().split()]
        print("yes" if group[s] == group[t] else "no")

def main():
    n, adj_mat = read_friends()
    group = divide_group(n, adj_mat)
    answer_queries(group)

if __name__ == '__main__':
    main()

#20でMLE（初）
あー
10000行×10000列の配列作ってるもんなあ・・・
行列でやろうと思ったらとたんにこれですよ
うかつすぎる