AtCoder Library Practice Contest 'A - Disjoint Set Union'時間超過の原因

前提・実現したいこと

ここに質問の内容を詳しく書いてください。
（例）PHP(CakePHP)で●●なシステムを作っています。
■■な機能を実装中に以下のエラーメッセージが発生しました。

発生している問題・エラーメッセージ

printを挿入して試したが、37行目のfor loop の二回目でTLEとなる。

該当のソースコード

python3
1def search(z, w):
2	i = 0
3	while i < len(con):
4		if z in con[i] and w in con[i]:
5			return 1
6			break
7		else:
8			 i += 1
9	return 0
10
11def add_edge(x, y):
12	j = 0
13	while j < len(con):
14		h = 0
15		if x in con[j]:
16			while h < len(con):
17				if y in con[h]:
18					con[j].extend(con[h])
19					del con[h]
20					break
21				else:
22					h += 1
23			con[j].append(y)
24		else:
25			while h < len(con):
26				if y in con[h]:
27					con[j].append(x)
28					break
29				else:
30					h += 1
31		con.append([x, y])
32
33N, Q = map(int, input().split())
34
35con = [[]]
36
37for i in range(Q):
38	t, u, v=map(int, input().split())
39	
40	if t == 0:
41		if search(u, v) == 0:
42			add_edge(u, v)
43		print(con)
44		
45	elif t == 1:
46		print(search(u, v))
47

試したこと

各所にprintを挿入して検証したが、37行目のfor loop一回目は正常。二回目のt,u,v取得時にTLE。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

行動規範の内容に同意します

回答1件

ベストアンサー

Python
1def add_edge(x, y):
2    j = 0
3    while j < len(con):

これ以降jが変更されないので無限ループになります。

投稿2021/05/01 14:05

yudedako67

総合スコア2047

あなたの回答

tips

プレビュー

行動規範の内容に同意します

質問の解決につながる回答をしましょう。サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。また、読む側のことを考えた、分かりやすい文章を心がけましょう。

15分調べてもわからないことは
teratailで質問しよう！

ただいまの回答率
85.48%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう！