ALDS1_11_D: Connected Components(続き)
行列でやろうと思ったらとたんにこれですよ
Setでやってみたら再帰が深すぎるエラー
今度は100000レベルかー
再帰じゃダメかなあ
こんな感じだから末尾再帰な形ではあると思うんだけど
def divide_group(n, adj_list):
group = [None] * n
def visit(k, g):
group[k] = g
for t in adj_list[k]:
if group[t] is None:
visit(t, g)
for k in range(n):
if group[k] is None:
visit(k, k)
return group
再帰からスタックを使ったループに変換してやっとAC
def read_friends():
n, m = [int(x) for x in input().split()]
adj_list = [set() for _ in range(n)]
for _ in range(m):
s, t = [int(x) for x in input().split()]
adj_list[s].add(t)
adj_list[t].add(s)
return n, adj_list
def divide_group(n, adj_list):
group = [None] * n
def visit(k, g):
S = [k]
while S:
k = S.pop()
group[k] = g
for t in adj_list[k]:
if group[t] is None:
S.append(t)
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_list = read_friends()
group = divide_group(n, adj_list)
answer_queries(group)
if __name__ == '__main__':
main()
エッジの数が少ない疎なグラフでは、隣接リストによる表現が適しています。
わざわざここにきて隣接行列を使ってみようなどという愚か者はおるまいな?