連結成分

問題

実行時間制限: 1 sec / メモリ制限: 65536 KB
SNSの友達関係を入力し、双方向の友達リンクを経由してある人からある人へたどりつけるかどうかを判定するプログラムを作成せよ。

入力

  • \(1\) 行目にSNSユーザ数を表す整数 \(n\) と友達関係の数 \(m\) が空白区切りで与えられる。SNSの各ユーザーは \(0\) から \(n-1\) までのIDが付されている。
  • 続く \(m\) 行に \(1\) つの友達関係が各行に与えらえる。\(1\) つの友達関係は空白で区切られた \(2\) つの整数 \(s\)、\(t\) で与えられ、 \(s\) と \(t\) が友達であることを示す。
  • 続く \(1\) 行に、質問の数 \(q\) が与えられ、続く \(q\) 行に質問が与えられる。
  • 各質問は空白で区切られた \(2\) つの整数 \(s\)、\(t\) で与えられ、「 \(s\) から \(t\) へたどり着けますか?」という質問を意味する。

出力

  • 各質問について \(s\) から \(t\) にたどり着ける場合は \(Yes\) と、たどり着けない場合は \(No\) を出力せよ。

制約

  • \(2 \leqq n \leqq 10^5\)
  • \(0 \leqq m \leqq 10^5\)
  • \(1 \leqq q \leqq 10^4\)

例1

入力

\(10 \hspace{8px} 9\)
\(0 \hspace{8px} 1\)
\(0 \hspace{8px} 2\)
\(3 \hspace{8px} 4\)
\(5 \hspace{8px} 7\)
\(5 \hspace{8px} 6\)
\(6 \hspace{8px} 7\)
\(6 \hspace{8px} 8\)
\(7 \hspace{8px} 8\)
\(8 \hspace{8px} 9\)
\(3\)
\(0 \hspace{8px} 1\)
\(5 \hspace{8px} 9\)
\(1 \hspace{8px} 3\)

出力

\(Yes\)
\(Yes\)
\(No\)

【出典】
渡部有隆, Ozy, 秋葉拓哉他「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」287〜291頁

解答例(C++)

#include <bits/stdc++.h>
using namespace std;

int n, m, q;
vector<int> graph[100000];
vector<pair<int, int>> question;
int INF = -1;
// 未探索はINF
int group[100000];

void dfs(int i, int c) {
  group[i] = c;
  vector<int> v = graph[i];
  for (int j = 0; j < v.size(); j++) {
    if (group[v[j]] == INF) {
      dfs(v[j], c);
    }
  }
}

int main() {

  cin >> n >> m;

  // 配列を初期化
  for(int i = 0; i < n; i++) {
    group[i] = INF;
  }

  // 入力を受け取る
  for(int i = 0; i < m; i++) {
    int s, t;
    cin >> s >> t;
    graph[s].push_back(t);
    graph[t].push_back(s);
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    int s, t;
    cin >> s >> t;
    question.push_back(make_pair(s,t));
  }

  // 探索
  int id = 1;

  for (int i = 0; i < n; i++) {
    if (group[i] == INF) {
      dfs(i, ++id);
    }
  }

  // 探索結果を出力
  for (int i = 0; i < q; i++) {
    int s = question[i].first;
    int t = question[i].second;
    if (group[s] == group[t]) {
      cout << "Yes" << endl;
    } else{
      cout << "No" << endl;
    }
  }

  return 0;

}