連結グラフと連結成分について簡単にまとめてから、問題を解いていきます。

連結グラフ

グラフに含まれる全ての頂点が他のいずれかの頂点とリンクしているようなグラフを連結グラフと言います。こんな感じ。

f:id:programgenjin:20190317092041p:plain

連結成分

あるグラフの部分グラフのうち、極大で連結なものを連結成分と呼びます。G'がグラフGの極大で連結な部分グラフであるとは、G'を部分グラフに持つGの連結な部分グラフがG'以外にないことを言います。言葉で説明すると分かりにくいが、図で表すとこんな感じ。

f:id:programgenjin:20190317093115p:plain

枠で囲われた部分が連結成分。

問題を解いてみる

次の問題を解きます。

グラフの連結成分 | アルゴリズムとデータ構造 | Aizu Online Judge

指定された２つの頂点が、同じ連結成分に含まれるか？という問題です。グラフを格納するのには隣接リストを使います。隣接リストはC++のSTLのvectorを使って実装することにします。

方針としては、最初にグラフを連結成分に分け、それぞれに番号を振ります。すると、それぞれの頂点がどの連結成分に属しているか番号によって管理することができます。これによって、例えば頂点s, tが友人関係にあるかどうか調べるとき、sとtの属する連結成分が同じかどうか、番号を比較することによって簡単に判定することができます。

連結成分に番号を振る時には深さ優先探索を用います。頂点が訪問済みかどうか調べるためのフラッグとして、色を用います。

white：未訪問
black：訪問済み

解答例：

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

#define N 100000
#define WHITE 0  // 未訪問
#define BLACK 1  // 訪問ずみ

// 連結成分の番号を振る関数
void dfs(int n, int comp[], vector<int> G[]) {
  int i, j, vertex, neighbor, color[N];
  stack<int> S;
  // 初期状態
  for (i = 0; i < n; i++) color[i] = WHITE;

  for (i = 0; i < n; i++) {
    if (color[i] == WHITE) {
      // dfs
      S.push(i);
      while (!S.empty()) {
        vertex = S.top();
        S.pop();        
        color[vertex] = BLACK;  // 訪問済みにする
        comp[vertex] = i;  // 連結成分の番号を振る          
        for (j = 0; j < (int) G[vertex].size(); j++) {
          neighbor = G[vertex][j]; // 隣接している頂点：友人
          if (color[neighbor] == WHITE) S.push(neighbor);
        }
      }
    }
  }
}

int main() {
  int i, n, m, q, s, t;
  int comp[N];  // 連結成分の番号
  vector<int> G[N];  // グラフを表現する隣接リスト

  cin >> n >> m;
  // 隣接リストを作成
  for (i = 0; i < m; i++) {
    cin >> s >> t;
    G[s].push_back(t);
    G[t].push_back(s);
  }

  // グラフを連結成分に分ける
  dfs(n, comp, G);

  cin >> q;
  for (i = 0; i < q; i++) {
    cin >> s >> t;
    if (comp[s] == comp[t]) cout << "yes" << endl;
    else cout << "no" << endl;
  }
  
  return 0;
}