#-------- 入力例１ --------- N = 5 M = 4 edges = [(1, 3), (2, 4), (3, 4), (3, 5)] #--------------------------- # 隣接リストを作成 g = [[] for _ inrange(N)] for edge in edges: a = edge[0] - 1 b = edge[1] - 1 g[a].append(b) # 頂点 a に隣接する頂点として b を追加 g[b].append(a) # 頂点 b に隣接する頂点として a を追加
# 隣接リストの作成 G = [list() for i inrange(N + 1)] # G[i] は頂点 i に隣接する頂点のリスト for a, b in edges: G[a].append(b) # 頂点 a に隣接する頂点として b を追加 G[b].append(a) # 頂点 b に隣接する頂点として a を追加
[制約] 🔹$ 2 \leqq N \leqq 100000 $ 🔹$ 1 \leqq M \leqq 100000 $ 🔹$ 1 \leqq A_i < B_i \leqq N $
解き方・ソースコード
この問題は、隣接リストを作成する問題です。
隣接リストは、各頂点に対して隣接する頂点のリストを記録する方法です。
隣接リストは、メモリ使用量が少ないことが大きな特徴です。
[Google Colaboratory]
1 2 3 4 5 6 7 8 9 10 11 12 13 14
#-------- 入力例１ --------- N = 5# 頂点の数 M = 4# 辺の数 edges = [(1, 3), (2, 4), (3, 4), (3, 5)] # 隣接する頂点の組み合わせ #--------------------------- # 隣接リストの作成 G = [ list() for i inrange(N + 1) ] # G[i] は頂点 i に隣接する頂点のリスト for a, b in edges: G[a].append(b) # 頂点 a に隣接する頂点として b を追加 G[b].append(a) # 頂点 b に隣接する頂点として a を追加
# 頂点ごとに隣接する頂点を出力 for i inrange(1, N + 1): print('{}; [{}]'.format(i, ', '.join(map(str, G[i]))))
import random #-------- 入力例１ --------- N = 100000 X = [random.randint(1, 1500) for _ inrange(N)] Y = [random.randint(1, 1500) for _ inrange(N)] Q = 100000 A = [random.randint(1, 1500 - 1) for _ inrange(Q)] B = [random.randint(1, 1500 - 1) for _ inrange(Q)] C = [random.randint(A[i] + 1, 1500) for i inrange(Q)] D = [random.randint(B[i] + 1, 1500) for i inrange(Q)] #--------------------------- # 各座標にある点の数をカウント S = [[0] * 1501for i inrange(1501)] for i inrange(N): S[X[i]][Y[i]] += 1
# ２次元累積和を算出 T = [[0] * 1501for i inrange(1501)] for i inrange(1, 1501): for j inrange(1, 1501): T[i][j] = T[i][j - 1] + S[i][j] for j inrange(1, 1501): for i inrange(1, 1501): T[i][j] = T[i - 1][j] + T[i][j]
#-------- 入力例１ --------- H = 5 W = 5 N = 3 A = [1, 3, 2] B = [1, 3, 2] C = [3, 5, 4] D = [3, 5, 4] #--------------------------- # 各日について加算 X = [ [ 0 ] * (W + 2) for i inrange(H + 2) ] Z = [ [ 0 ] * (W + 2) for i inrange(H + 2) ] for t inrange(N): X[A[t]][B[t]] += 1 X[C[t] + 1][D[t] + 1] += 1 X[A[t]][D[t] + 1] -= 1 X[C[t] + 1][B[t]] -= 1
# 二次元累積和を算出 for i inrange(1, H + 1): for j inrange(1, W + 1): Z[i][j] = Z[i][j - 1] + X[i][j] for j inrange(1, W+1): for i inrange(1, H + 1): Z[i][j] = Z[i - 1][j] + Z[i][j]
# 出力 for i inrange(1, H + 1): for j inrange(1, W + 1): if j >= 2: print(' ', end='') print(Z[i][j], end='') print()
import random #--------- 入力例1 --------- N = 100# 座標の数 X = [random.randint(1, 1500) for _ inrange(N)] # 各X座標 Y = [random.randint(1, 1500) for _ inrange(N)] # 各Y座標
Q = 10# 質問の数 A = [random.randint(1, 750) for _ inrange(N)] # 座標範囲の開始X座標 B = [random.randint(1, 750) for _ inrange(N)] # 座標範囲の開始Y座標 C = [random.randint(750, 1500) for _ inrange(N)] # 座標範囲の終了X座標 D = [random.randint(750, 1500) for _ inrange(N)] # 座標範囲の終了Y座標 #--------------------------- # 各座標にある点の数を数える S = [[0] * 1501for i inrange(1501) ] for i inrange(N): S[X[i]][Y[i]] += 1
# 累積和をとる T = [[0] * 1501for i inrange(1501) ] for i inrange(1, 1501): for j inrange(1, 1501): T[i][j] = T[i][j - 1] + S[i][j] for j inrange(1, 1501): for i inrange(1, 1501): T[i][j] = T[i - 1][j] + T[i][j]