グラフの復習
前回行ったBFS、DFSについて復習しましょう。
以下の点を抑えていただければ、グラフの問題を解く際に役立つかと思います。
- グラフの辺と頂点を２次元配列で管理すること
- 探索を行う際に、起点にしている頂点と次に探索する頂点を意識すること
- BFS、DFSの違いを理解すること
BFS(幅優先探索)
- 最短経路の発見が得意。
- 先に見つけた頂点から探索。
- queueを使って実装する。
DFS(深さ優先探索)
- より深い頂点を優先して探索。
- stackを使って実装する。
グラフ探索のテンプレート
BFS(幅優先探索)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u); // 無向グラフの場合
}
vector<int> dist(n, -1);
queue<int> q;
int start = 0; // 開始点を0とする
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int i = 0; i < g[v].size(); i++) {
int next = g[v][i];
if (dist[next] == -1) {
dist[next] = dist[v] + 1;
q.push(next);
}
}
}
// 距離配列の出力をする場合
for (int i = 0; i < n; i++) {
cout << i << ' ' << dist[i] << endl;
}
return 0;
}
グリッドを探索する場合
#include <bits/stdc++.h>
using namespace std;
// 移動方向（上下左右）
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
int main() {
int h, w;
cin >> h >> w;
vector<string> grid(h);
for (int i = 0; i < h; i++) {
cin >> grid[i];
}
vector<vector<int>> dist(h, vector<int>(w, -1));
queue<pair<int, int>> q;
// 0,0を開始点として設定
dist[0][0] = 0;
q.push({0, 0});
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
// 上下左右の隣接セルを探索
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
// グリッドの範囲内かつ未訪問で'.'のセルならば進む
if (nx >= 0 && nx < h && ny >= 0 && ny < w && grid[nx][ny] == '.' && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
// 距離配列の出力をする場合
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (dist[i][j] == -1) {
cout << "# ";
} else {
cout << dist[i][j] << " ";
}
}
cout << endl;
}
return 0;
}
DFS(深さ優先探索)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u); // 無向グラフの場合
}
vector<int> dist(n, -1);
stack<int> s;
int start = 0; // 開始点を0とする
dist[start] = 0;
s.push(start);
while (!s.empty()) {
int v = s.top();
s.pop();
for (int i = 0; i < g[v].size(); i++) {
int next = g[v][i];
if (dist[next] == -1) {
dist[next] = dist[v] + 1;
s.push(next);
}
}
}
// 距離配列の出力をする場合
for (int i = 0; i < n; i++) {
cout << i << ' ' << dist[i] << endl;
}
return 0;
}
グリッドを探索する場合
#include <bits/stdc++.h>
using namespace std;
// 移動方向（上下左右）
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
int main() {
int h, w;
cin >> h >> w;
vector<string> grid(h);
for (int i = 0; i < h; i++) {
cin >> grid[i];
}
vector<vector<int>> dist(h, vector<int>(w, -1));
stack<pair<int, int>> s;
// 0,0を開始点として設定
dist[0][0] = 0;
s.push({0, 0});
while (!s.empty()) {
auto [x, y] = s.top();
s.pop();
// 上下左右の隣接セルを探索
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
// グリッドの範囲内かつ未訪問で'.'のセルならば進む
if (nx >= 0 && nx < h && ny >= 0 && ny < w && grid[nx][ny] == '.' && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
s.push({nx, ny});
}
}
}
// 距離配列の出力をする場合
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (dist[i][j] == -1) {
cout << "# ";
} else {
cout << dist[i][j] << " ";
}
}
cout << endl;
}
return 0;
}
演習問題
以下の問題から2~3問解いて、グラフ探索の復習をしてみましょう。
Union-Find
Union-Findで出来ること
- 要素をグループに分ける
- グループをまとめる
- 2つの要素が同じグループに属しているかどうかを判定する
- 上記の操作を高速に行える。
計算量は、で、はアッカーマン関数の逆関数で、ほぼ定数時間で処理できる。以下と考えても問題ない。
木構造について
Union-Findは木構造を使ってグループを管理します。 木構造とは、要素を頂点とし、要素間の関係を辺で表現したデータ構造です。 すべての頂点が少なくとも1つの辺でつながっており、閉路（輪になっている部分）が存在しないグラフです。N個の頂点を持つ木構造はN-1本の辺を持ちます。
Union-Findの実装
#include <bits/stdc++.h>
using namespace std;
// Union-Findで用いる配列を宣言
// parent[i]はiの親の番号を表す
// treeRank[i]はiを根とする木の高さを表す
vector<int> parent, treeRank;
// 初期化: N個の要素でUnion-Findを初期化する
void init(int n) {
parent.resize(n);
treeRank.resize(n, 1);
for (int i = 0; i < n; ++i) parent[i] = i;
}
// find関数: xの属する集合の根を見つける（経路圧縮）
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 経路圧縮
}
return parent[x];
}
// unite関数: 2つの要素xとyの属する集合を結合する
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (treeRank[rootX] > treeRank[rootY]) {
parent[rootY] = rootX;
} else if (treeRank[rootX] < treeRank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
treeRank[rootX]++;
}
}
}
// same関数: 2つの要素xとyが同じ集合に属するかを判定
bool same(int x, int y) {
return find(x) == find(y);
}
int main() {
int N, Q; // N: 頂点数, Q: クエリ数
cin >> N >> Q;
// Union-FindをN個の頂点で初期化
init(N);
for (int i = 0; i < Q; ++i) {
int type, A, B;
cin >> type >> A >> B;
if (type == 0) {
// 連結クエリ（type = 0）の場合
unite(A, B);
} else {
// 判定クエリ（type = 1）の場合
if (same(A, B)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
}
return 0;
}
classを使った実装
#include <bits/stdc++.h>
using namespace std;
// Union-Findのクラス定義
class UnionFind {
private:
vector<int> parent, rank;
public:
// n個の要素でUnion-Findを初期化する
UnionFind(int n) : parent(n), rank(n, 1) {
// 自分を親として初期化
for (int i = 0; i < n; ++i) parent[i] = i;
}
// find関数: xの属する集合の根を見つける
// 経路圧縮を使って、探索したノードの親を根に直接つなぐ
int find(int x) {
// 自分自身が親でない場合、再帰的に親を見つける
if (parent[x] != x) {
parent[x] = find(parent[x]); // 親を根に変更（経路圧縮）
}
return parent[x]; // 最終的な根を返す
}
// unite関数: 2つの要素xとyの属する集合を結合する
void unite(int x, int y) {
// それぞれの根を見つける
int rootX = find(x);
int rootY = find(y);
// 異なる集合なら結合する
if (rootX != rootY) {
// ランクを使って、高い木に低い木を接続することで木の高さを抑える
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX; // rootYの親をrootXに設定
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY; // rootXの親をrootYに設定
} else {
// ランクが同じ場合はrootYをrootXに接続し、rootXのランクを1増やす
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
// same関数: 2つの要素xとyが同じ集合に属するかを判定
bool same(int x, int y) {
return find(x) == find(y); // 根が同じなら同じ集合に属する
}
};
int main() {
int N, Q; // N: 頂点数, Q: クエリ数
cin >> N >> Q;
// Union-Findのインスタンスを作成し、N個の頂点を管理する
UnionFind uf(N);
for (int i = 0; i < Q; ++i) {
int type, A, B;
cin >> type >> A >> B; // クエリの種類と対象の頂点A, Bを入力
if (type == 0) {
// 連結クエリ（type = 0）の場合
// 頂点Aと頂点Bの間に辺を追加（同じ集合に結合）
uf.unite(A, B);
} else {
// 判定クエリ（type = 1）の場合
// 頂点Aと頂点Bが連結かどうかを判定
if (uf.same(A, B)) {
// 連結であれば"Yes"を出力
cout << "Yes" << endl;
} else {
// 連結でなければ"No"を出力
cout << "No" << endl;
}
}
}
return 0;
}