Loading...

プレビュー

全43ステップ中13ステップのみ表示

ログインして全て見る

SNS友達グループ

中級

SNS Friend Groups

DFSを使用して接続された友達グループの数を見つける問題

📊 計算量

区分	計算量
平均	O(N²)
最悪	O(N²)
空間	O(N)

🏷️ Tags

DFSグラフ連結成分ソーシャルネットワーク

📋 問題

SNS友達グループ探し

新しいSNSサービスでユーザーの友達関係が与えられます。直接の友達、または友達の友達で繋がっているユーザーは同じグループです。全体の友達グループの数を求めてください。

1/43

Loading...

👥SNS友達関係分析!

7人のユーザーの中に何個の友達グループがあるか探しましょう!

🔒

SNS友達グループ探し

問題説明

新しいSNSサービスでユーザーの友達関係が与えられます。直接の友達、または友達の友達で繋がっているユーザーは同じグループです。全体の友達グループの数を求めてください。

入力

ユーザー数 N (1 ≤ N ≤ 200) N×N 友達関係行列 (friends[i][j] = 1ならiとjは友達)

出力

友達グループの総数

制約条件

•1 ≤ N ≤ 200
•friends[i][i] = 1 (自分自身)
•friends[i][j] = friends[j][i] (対称)

例

例 1

入力

7
[[1,1,0,0,0,0,0],
 [1,1,1,0,0,0,0],
 [0,1,1,0,0,0,0],
 [0,0,0,1,1,0,0],
 [0,0,0,1,1,0,0],
 [0,0,0,0,0,1,1],
 [0,0,0,0,0,1,1]]

出力

説明

グループ1: {ミンス、ジヨン、スジン}, グループ2: {ヒョヌ、ソヨン}, グループ3: {ジュノ、イェウン} → 3グループ

SNS友達グループ | AlgoNote