upper_boundとlower_bound

ソート済みのvector Aに対して

hoge以上の最小の要素のイテレータ

lower_bound(A.begin(), A.end(), hoge)

hogeを超える最小の要素のイテレータ

upper_bound(A.begin(), A.end(),hoge)

値がhoge以上の要素の個数

A.end() - lower_bound(A.begin(), A.end(), hoge)

値がhogeより大きい要素の個数

A.end() - upper_bound(A.begin(), A.end(), hoge)

値がhoge以下の要素の個数

upper_bound(A.begin(),A.end(),hoge)-A.begin()

値がhoge未満の要素の個数

lower_bound(A.begin(),A.end(),hoge)-A.begin()

値がhoge以上で最小の要素

*lower_bound(A.begin(), A.end(), hoge)

値がhogeより大きくて最小の要素

*upper_bound(A.begin(), A.end(), hoge)

値がhoge以下で最大の要素

*--upper_bound(A.begin(), A.end(), hoge)

値がhoge未満で最大の要素

*--lower_bound(A.begin(), A.end(), hoge)

値がhoge1以上でhoge2以下の要素の個数

upper_bound(A.begin(), A.end(), hoge2) -lower_bound(A.begin(), A.end(), hoge1)

値がhoge1より大きくてhoge2未満の要素の個数

lower_bound(A.begin(), A.end(), hoge2) - upper_bound(A.begin(), A.end(), hoge1)

値がhoge1以上でhoge2未満の要素の個数

lower_bound(A.begin(), A.end(), hoge2) - lower_bound(A.begin(), A.end(), hoge1)

値がhoge1より大きくてhoge2以下の要素の個数

upper_bound(A.begin(), A.end(), hoge2) - upper_bound(A.begin(), A.end(), hoge1)

値がhogeと等しい要素の個数

upper_bound(A.begin(), A.end(), hoge) -lower_bound(A.begin(), A.end(), hoge)

二次元累積和

二次元累積和とは

このような配列を考える。これを配列Aとする。

配列Aの中の任意の長方形の区間の総和を求めたいとする。
例

図の水色のマスの合計は、1+5+2+6+3+9+3+8=37である。
これは、A[1][2]からA[2][5]までの総和といえる。
これをΣ([1][2],[2][5])と書くことにする。
次の関係式が成り立つ。
Σ([1][2],[2][5])=Σ([0][0],[2][5])-Σ([0][0],[0][5])-Σ([0][0],[2][1])+Σ([0][0],[0][1])

一般化すると次のようになる。
Σ([a][b],[c][d])=Σ([0][0],[c][d])-Σ([0][0],[a-1][d])-Σ([0][0],[c][b-1])+Σ([0][0],[a-1][b-1])

Σ([0][0],[i][j])=S[i][j]とする。(これが二次元累積和)
そうすると
Σ([a][b],[c][d])=S[c][d]-S[a-1][d]-S[c][b-1]+S[a-1][b-1]
となり、Sを前計算で作っておけばO(1)で長方形の区間が求まる。

二次元累積和の作り方

S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i][j]
という漸化式が成り立つ。(図を見ながら確認すればわかる。)
よってインデックスが小さいほうから埋めていけばO(HW)で作成できる。
i=0またはj=0の時は配列外参照になるため別の処理が必要である。
(i)i=0かつj=0の時
S[i][j]=A[i][j]
(ii)i=0かつj≠0の時
S[i][j]=S[i][j-1]+A[i][j]
(iii)i≠0かつj=0の時
S[i][j]=S[i-1][j]+A[i][j]

コード例

図の水色の部分の総和を求める。(答えは37)

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>

using namespace std;

#define INF LLONG_MAX / 5
#define int long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define enld endl

signed main() {
	vector<vector<int>>A;
	A = {
		{1,5,8,4,7,4,2},
		{4,7,1,5,2,6,4},
		{8,2,3,9,3,8,1},
		{3,5,6,1,7,9,2}
	};
	int H = 4, W = 7;

	//二次元累積和の作成
	vector<vector<int>>S(H, vector<int>(W));
	rep(i, H) {
		rep(j, W) {
			if (i == 0 && j == 0) {
				S[i][j] = A[i][j];
			}
			else if (i == 0 && j != 0) {
				S[i][j] = S[i][j - 1] + A[i][j];
			}
			else if (i != 0 && j == 0) {
				S[i][j] = S[i - 1][j] + A[i][j];
			}
			else {
				S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j];
			}
		}
	}

	int a = 1, b = 2, c = 2, d = 5;
	//Σ([a][b],[c][d])を出力
	//Σ([a][b],[c][d])=S[c][d]-S[a-1][d]-S[c][d-1]+S[a-1][b-1]
	cout << S[c][d] - S[a - 1][d] - S[c][b - 1] + S[a - 1][b - 1];
}

37が出力された。

コーナーケース

Σ([a][b],[c][d])=S[c][d]-S[a-1][d]-S[c][b-1]+S[a-1][b-1]
なのでa=0またはb=0の時は配列外参照になる。
この時は特別な処理が必要である。
(i)a=0かつb=0の時
Σ([a][b],[c][d])=S[c][d]
(ii)a=0かつb≠0の時
Σ([a][b],[c][d])=S[c][d]-S[c][b-1]
(iii)a≠0かつb=0の時
Σ([a][b],[c][d])=S[c][d]-S[a-1][d]

となる。

問題

1行目にH Wが空白区切りで与えられる。
2行目以降に二次元配列が与えられる。
次に整数Qが与えられる。
その次のQ行でa b c dが与えられる。(0-index)
それぞれについてΣ([a][b],[c][d])を求めよ。

入力
H W
A[0][0]　・・・　A[0][W-1]
・
・
・
A[H-1][0]　・・・　A[H-1][W-1]
Q
a_1 b_1 c_1 d_1
・
・
・
a_Q b_Q c_Q d_Q

入力例
4 7
1 5 8 4 7 4 2
4 7 1 5 2 6 4
8 2 3 9 3 8 1
3 5 6 1 7 9 2
5
1 2 2 5
1 6 1 6
0 0 0 3
0 1 1 2
3 0 3 5

出力例
37
4
18
21
31

正解コード

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>

using namespace std;

#define INF LLONG_MAX / 5
#define int long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define enld endl

signed main() {
	int H, W;
	cin >> H >> W;
	vector<vector<int>>A(H, vector<int>(W));
	rep(i, H) {
		rep(j, W) {
			cin >> A[i][j];
		}
	}
	//二次元累積和の作成
	vector<vector<int>>S(H, vector<int>(W));
	rep(i, H) {
		rep(j, W) {
			if (i == 0 && j == 0) {
				S[i][j] = A[i][j];
			}
			else if (i == 0 && j != 0) {
				S[i][j] = S[i][j - 1] + A[i][j];
			}
			else if (i != 0 && j == 0) {
				S[i][j] = S[i - 1][j] + A[i][j];
			}
			else {
				S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j];
			}
		}
	}
	int Q;
	cin >> Q;
	int a, b, c, d;
	rep(_, Q) {
		cin >> a >> b >> c >> d;
		if (a == 0 && b == 0) {
			cout << S[c][d] << endl;
		}
		else if (a == 0 && b != 0) {
			cout << S[c][d] - S[c][b - 1] << endl;
		}
		else if (a != 0 && b == 0) {
			cout << S[c][d] - S[a - 1][d] << endl;
		}
		else {
			cout << S[c][d] - S[a - 1][d] - S[c][b - 1] + S[a - 1][b - 1] << endl;
		}
	}
}

グラフアルゴリズムのライブラリ[1]

グリッド

グリッド上のBFS(最短経路)

//各点のスタートからの距離を配列で返す
//si,sj:スタートの座標
//スタートは壁ではない
//辿り着けない:-1
vector<vector<int>>bfs_grid_pass(int si,int sj, vector<vector<char>>field) {
	vector<int>di;
	di = { 0,1,0,-1 };
	vector<int>dj;
	dj = { 1,0,-1,0 };
	int h = field.size();
	int w = field[0].size();
	vector<vector<int>> d(h, vector<int>(w, INF));
	d[si][sj] = 0;
	queue<pair<int,int>> que;
	que.push(pair<int,int>(si, sj));
	while (!que.empty()) {
		pair<int,int> pos = que.front();
		que.pop();
		int i = pos.first, j = pos.second;
		for (int k = 0; k < 4; k++) {
			int ni = i + di[k], nj = j + dj[k];
			if (ni < 0 || ni >= h) continue;
			if (nj < 0 || nj >= w) continue;
			if (field[ni][nj] == '#') continue;
			if (d[ni][nj] > d[i][j] + 1) {
				d[ni][nj] = d[i][j] + 1;
				que.push(pair<int,int>(ni, nj));
			}
		}
	}
	rep(i, h) {
		rep(j, w) {
			if (d[i][j] == INF) {
				d[i][j] = -1;
			}
		}
	}
	return d;
}

コード例

//各点のスタートからの距離を配列で返す
//si,sj:スタートの座標
//スタートは壁ではない
//辿り着けない:-1
vector<vector<int>>bfs_grid_pass(int si,int sj, vector<vector<char>>field) {
	vector<int>di;
	di = { 0,1,0,-1 };
	vector<int>dj;
	dj = { 1,0,-1,0 };
	int h = field.size();
	int w = field[0].size();
	vector<vector<int>> d(h, vector<int>(w, INF));
	d[si][sj] = 0;
	queue<pair<int,int>> que;
	que.push(pair<int,int>(si, sj));
	while (!que.empty()) {
		pair<int,int> pos = que.front();
		que.pop();
		int i = pos.first, j = pos.second;
		for (int k = 0; k < 4; k++) {
			int ni = i + di[k], nj = j + dj[k];
			if (ni < 0 || ni >= h) continue;
			if (nj < 0 || nj >= w) continue;
			if (field[ni][nj] == '#') continue;
			if (d[ni][nj] > d[i][j] + 1) {
				d[ni][nj] = d[i][j] + 1;
				que.push(pair<int,int>(ni, nj));
			}
		}
	}
	rep(i, h) {
		rep(j, w) {
			if (d[i][j] == INF) {
				d[i][j] = -1;
			}
		}
	}
	return d;
}

void print_vector(vector<vector<int>>V) {
	rep(i, V.size()) {
		rep(j, V[i].size()) {
			cout << V[i][j];
			if (j == V[i].size() - 1) {
				cout << endl;
			}
			else {
				cout << ' ';
			}
		}
	}
}

signed main() {
	int h, w;
	cin >> h >> w;
	int si, sj;
	cin >> si >> sj;
	vector<vector<char>>field(h, vector<char>(w));
	rep(i, h) {
		rep(j, w) {
			cin >> field[i][j];
		}
	}
	vector<vector<int>>d = bfs_grid_pass(si, sj, field);
	print_vector(d);
}

入力
7 8
1 1
########
#......#
#.######
#..#...#
#..##..#
##.....#
########

出力
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 1 2 3 4 5 -1
-1 1 -1 -1 -1 -1 -1 -1
-1 2 3 -1 11 10 11 -1
-1 3 4 -1 -1 9 10 -1
-1 -1 5 6 7 8 9 -1
-1 -1 -1 -1 -1 -1 -1 -1

グリッド上のBFS(色分け)

//0から始まる数字で色分けする
//壁:-1
vector<vector<int>>bfs_grid_color(vector<vector<char>>field) {
	int color = 0;
	int h = field.size();
	int w = field[0].size();
	vector<vector<int>> COLOR(h, vector<int>(w, INF));
	vector<int>di;
	di = { 0,1,0,-1 };
	vector<int>dj;
	dj = { 1,0,-1,0 };
	rep(si, h) {
		rep(sj, w) {
			if (field[si][sj] != '#') {
				if(COLOR[si][sj]==INF){
				COLOR[si][sj] = color;
				queue<pair<int, int>> que;
				que.push(pair<int, int>(si, sj));
				while (!que.empty()) {
					pair<int, int> pos = que.front();
					que.pop();
					int i = pos.first, j = pos.second;
					for (int k = 0; k < 4; k++) {
						int ni = i + di[k], nj = j + dj[k];
						if (ni < 0 || ni >= h) continue;
						if (nj < 0 || nj >= w) continue;
						if (field[ni][nj] == '#') continue;
						if (COLOR[ni][nj] > COLOR[i][j] + 1) {
							COLOR[ni][nj] = color;
							que.push(pair<int, int>(ni, nj));
						}
					}
				}
				color++;
				}
			}
		}
	}
	rep(i, h) {
		rep(j, w) {
			if (COLOR[i][j] == INF) {
				COLOR[i][j] = -1;
			}
		}
	}
	return COLOR;
}

コード例

//0から始まる数字で色分けする
//壁:-1
vector<vector<int>>bfs_grid_color(vector<vector<char>>field) {
	int color = 0;
	int h = field.size();
	int w = field[0].size();
	vector<vector<int>> COLOR(h, vector<int>(w, INF));
	vector<int>di;
	di = { 0,1,0,-1 };
	vector<int>dj;
	dj = { 1,0,-1,0 };
	rep(si, h) {
		rep(sj, w) {
			if (field[si][sj] != '#') {
				if(COLOR[si][sj]==INF){
				COLOR[si][sj] = color;
				queue<pair<int, int>> que;
				que.push(pair<int, int>(si, sj));
				while (!que.empty()) {
					pair<int, int> pos = que.front();
					que.pop();
					int i = pos.first, j = pos.second;
					for (int k = 0; k < 4; k++) {
						int ni = i + di[k], nj = j + dj[k];
						if (ni < 0 || ni >= h) continue;
						if (nj < 0 || nj >= w) continue;
						if (field[ni][nj] == '#') continue;
						if (COLOR[ni][nj] > COLOR[i][j] + 1) {
							COLOR[ni][nj] = color;
							que.push(pair<int, int>(ni, nj));
						}
					}
				}
				color++;
				}
			}
		}
	}
	rep(i, h) {
		rep(j, w) {
			if (COLOR[i][j] == INF) {
				COLOR[i][j] = -1;
			}
		}
	}
	return COLOR;
}

void print_vector(vector<vector<int>>V) {
	rep(i, V.size()) {
		rep(j, V[i].size()) {
			cout << V[i][j];
			if (j == V[i].size() - 1) {
				cout << endl;
			}
			else {
				cout << ' ';
			}
		}
	}
}

signed main() {
	int h, w;
	cin >> h >> w;
	vector<vector<char>>field(h, vector<char>(w));
	rep(i, h) {
		rep(j, w) {
			cin >> field[i][j];
		}
	}
	vector<vector<int>>COLOR(h, vector<int>(w));
	COLOR = bfs_grid_color(field);
	print_vector(COLOR);
}

入力
4 4
..#.
..#.
.#..
.#..
出力
0 0 -1 1
0 0 -1 1
0 -1 1 1
0 -1 1 1

グラフ

これ以降は隣接リストを使う
以前の記事で隣接リストに二次元vectorを使ったがsetを使った方が便利なので変える
※補足
隣接リストの作り方(重みなしグラフ)
setのvectorにする。

a bと入力されるとする
これは頂点aと頂点bが繋がっているということである。

コード

signed main() {
	int V;//頂点数
	int E;//辺の数
	cin >> V >> E;
	vector<set<int>>G(V);//隣接リスト
	for (int i = 0; i < E; i++) {
		int a, b;
		cin >> a >> b;
		G[a].insert(b);
		G[b].insert(a);
	}

	rep(i, V) {
		for (auto x : G[i]) {
			cout << x << ' ';
		}
		cout << endl;
	}

}

入力
8 7
0 3
1 3
1 2
3 7
3 4
7 4
5 6

出力
3
2 3
1
0 1 4 7
3 7
6
5
3 4

BFS(最短経路)

//スタートからの距離を配列で返す
//start:スタートの頂点番号
//辿り着けない:-1
vector<int>bfs_graph_pass(int start, vector<set<int>>G) {
	int V = G.size();
	vector<int>dist(V, INF);
	queue<int> que;
	dist[start] = 0;
	que.push(start);
	while (!que.empty()) {
		int v = que.front();
		que.pop();
		for (auto nv : G[v]) {
			if (dist[nv] != INF)continue;
			dist[nv] = dist[v] + 1;
			que.push(nv);
		}
	}
	rep(i, V) {
		if (dist[i] == INF) {
			dist[i] = -1;
		}
	}
	return dist;
}

コード例

//スタートからの距離を配列で返す
//start:スタートの頂点番号
//辿り着けない:-1
vector<int>bfs_graph_pass(int start, vector<set<int>>G) {
	int V = G.size();
	vector<int>dist(V, INF);
	queue<int> que;
	dist[start] = 0;
	que.push(start);
	while (!que.empty()) {
		int v = que.front();
		que.pop();
		for (auto nv : G[v]) {
			if (dist[nv] != INF)continue;
			dist[nv] = dist[v] + 1;
			que.push(nv);
		}
	}
	rep(i, V) {
		if (dist[i] == INF) {
			dist[i] = -1;
		}
	}
	return dist;
}


signed main() {
	int start;
	cin >> start;
	int V;//頂点数
	int E;//辺の数
	cin >> V >> E;
	vector<set<int>>G(V);//隣接リスト
	for (int i = 0; i < E; i++) {
		int a, b;
		cin >> a >> b;
		G[a].insert(b);
		G[b].insert(a);
	}

	vector<int>dist = bfs_graph_pass(start, G);
	rep(i, V) {
		cout << dist[i] << ' ';
	}

}

入力
0
8 7
0 3
1 3
1 2
3 7
3 4
7 4
5 6

出力
0 2 3 1 2 -1 -1 2

BFS(色分け)

0から始まる数字で連結成分ごとに色分けする。

//0から始まる数字で色分けして配列で返す
vector<int>bfs_graph_color(vector<set<int>>G) {
	int color = 0;
	int V = G.size();
	vector<int>COLOR(V, INF);
	rep(start, V) {
		if (COLOR[start] == INF) {
			queue<int> que;
			COLOR[start] = color;
			que.push(start);
			while (!que.empty()) {
				int v = que.front();
				que.pop();
				for (auto nv : G[v]) {
					if (COLOR[nv] != INF)continue;
					COLOR[nv] = color;
					que.push(nv);
				}
			}
			color++;
		}
	}
	return COLOR;
}

コード例

//0から始まる数字で色分けして配列で返す
vector<int>bfs_graph_color(vector<set<int>>G) {
	int color = 0;
	int V = G.size();
	vector<int>COLOR(V, INF);
	rep(start, V) {
		if (COLOR[start] == INF) {
			queue<int> que;
			COLOR[start] = color;
			que.push(start);
			while (!que.empty()) {
				int v = que.front();
				que.pop();
				for (auto nv : G[v]) {
					if (COLOR[nv] != INF)continue;
					COLOR[nv] = color;
					que.push(nv);
				}
			}
			color++;
		}
	}
	return COLOR;
}


signed main() {
	int V;//頂点数
	int E;//辺の数
	cin >> V >> E;
	vector<set<int>>G(V);//隣接リスト
	for (int i = 0; i < E; i++) {
		int a, b;
		cin >> a >> b;
		G[a].insert(b);
		G[b].insert(a);
	}
	vector<int>COLOR = bfs_graph_color(G);
	rep(i, V) {
		cout << COLOR[i] << ' ';
	}
}

入力
8 7
0 3
1 3
1 2
3 7
3 4
7 4
5 6

出力
0 0 0 0 0 1 1 0

bit全探索のテンプレートと拡張版

(1)N個の0,1から成る2^N個の配列を生成

int N;
cin >> N;
for (int S = 0; S < 1 << N; S++) {
	//作成
	vector<int>A;
	rep(i, N) {
		A.push_back(S >> i & 1);
	}
	//操作
	rep(i, N) {
		cout << A[i] << ' ';
	}
	cout << endl;
}

入力例
3
出力例
0 0 0
1 0 0
0 1 0
1 1 0
0 0 1
1 0 1
0 1 1
1 1 1

(2)N個の0,1…M-1から成るM^N個の配列を生成

int N;
int M;
cin >> N >> M;
for (int S = 0; S < pow(M,N); S++) {
	//作成
	int s = S;
	vector<int>A;
	rep(i, N) {
		A.push_back(s%M);
		s /= M;
	}
	//操作
	rep(i, N) {
		cout << A[i] << ' ';
	}
	cout << endl;
}

入力例
2 3
出力例
0 0
1 0
2 0
0 1
1 1
2 1
0 2
1 2
2 2

ABC146 D - Coloring Edges on Tree

(1)問題

atcoder.jp

(2)問題概要

1からNまでの番号がついたN頂点の木Gが与えられる。Gの辺を何色かで塗り分ける。一つの頂点から出る辺は全て違う色にするとき最小で何色で塗り分けられるかを求め、塗り方を一つ構築せよ。

(3)前提知識

・N頂点の木の辺の数はN-1個（一つの頂点に辺と頂点のペアが何個かくっついていると考えるとイメージできる。）

(4)解法

まず、最小で何色で塗り分けられるかを求める。各頂点から出る辺の数のうち最大の数をMとする。適当な頂点を根として親から子の方向に色を塗っていくと考えると根は子に全て違う色の辺を繋ぎ、他の頂点は親から繋がれた頂点と違う色で子に全て違う色の辺を渡す必要がある。M色あれば全ての頂点で条件を満たすように塗れるので必要な色の数の最小値はMであることが分かる。

次に塗り方の構築を考える。作るものは繋がれている頂点と辺の色がペアとなっている隣接リストである。この隣接リストが作れたらこれを参照して問題で求められている出力をすることができる。計算量を減らすために作る隣接リストはpairではなくmapにする。つまりN個のmapからなる配列MCを作り、MC[i]にはkeyがiから繋がれている頂点、valueが辺の色であるmapが入っている。

色は貪欲に塗っていけばいい。つまりMC[i]のまだ塗られていない要素のvalueに0,1,2,...と順に色を振り分けていけばいいがMC[i]のもうすでに塗られている色は塗ってはいけない。ある色がMC[i]のvalueにもう存在するかの判定にsetを使う。すなわちN個のsetの配列SCを持っておき、SC[i]には頂点iから出る辺にもうすでに塗られた色を入れておく。そしてMC[i]に色を追加していくときにはSC[i]を参照すればもう使われている色が分かる。

MCに対するvalueの更新の仕方を整理する。塗る色を持つcolorという整数の変数を用意しておき、各MC[i]についてcolorを0からはじめ、塗ったらcolorを1増やす。塗るときはMC[i][key]のvalueをcolorに変更すると同時にMC[key][value]の値をcolorに変更する。さらにSC[i]とSC[key]にcolorを挿入する。colorで塗れるかはSC[i]にcolorが存在するかで判定し、存在する場合は塗れないので塗らずにcolorを1増やす。

(5)ソースコード

int V;
cin >> V;
int E = V - 1;//辺の数
vector<int>A(E);
vector<int>B(E);
rep(i, E) {
	cin >> A[i] >> B[i];
         //0-index にする
	A[i]--;
	B[i]--;
}
vector<vector<int>>G(V);//隣接リスト
rep(i, E) {
	G[A[i]].push_back(B[i]);
	G[B[i]].push_back(A[i]);
}
int max_color = 0;
rep(i, V) {
	max_color = max(max_color, int(G[i].size()));
}

vector<set<int>>SC(V);
vector<map<int, int>>MC(V);
rep(i, V) {
	rep(j, G[i].size()) {
		MC[i][G[i][j]] = -1;//色を-1(まだ塗られていない)で初期化
	}
}

int color = 0;
map<int, int>::iterator it;
rep(i, V) {
	color = 0;
	for (it = MC[i].begin(); it != MC[i].end(); it++) {
		if (it->second == -1) {
			while (1) {
				if (SC[i].count(color)) {
					color++;
				}
				else {
					it->second = color;
					MC[it->first][i] = color;
					SC[i].insert(color);
					SC[it->first].insert(color);
					break;
				}
			}
		}
	}
}

cout << max_color << endl;
rep(i, E) {
	cout << MC[A[i]][B[i]] + 1 << endl;
}

Union-Find木の使い方

Union-Find木の書き方、使い方をまとめた

Union-Find木は、以下のことができるデータ構造である。

1, 要素aと要素bのグループを併合する。
2, 要素aと要素bが同じグループに入っているか判定する。

(1)書き方

main関数の上に次のように書く

class UnionFindTree {
private:
	std::vector<int> par;   // 親
	std::vector<int> depth; // 木の深さ

public:
	// n要素で初期化
	UnionFindTree(int n) {
		for (int i = 0; i < n; i++) {
			par.push_back(i);
			depth.push_back(0);
		}
	}

	// 木の根を求める
	int find(int x) {
		if (par[x] == x) {
			return x;
		}
		else {
			return par[x] = find(par[x]);
		}
	}

	// xとyの属する集合を併合
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y)
			return;

		if (depth[x] < depth[y]) {
			par[x] = y;
		}
		else {
			par[y] = x;
			if (depth[x] == depth[y])
				depth[x]++;
		}
	}

	// xとyが同じ集合に属するか否か
	bool same(int x, int y) { return find(x) == find(y); }
};

(2)使い方

[例]次の図のような構造を考える。

図1 : Union-Find木で表現するデータ

この集合は、次のように3つのグループに分けることができる。

(0,1,2,3)
(4,5,6)
(7)

※同じグループ同士は辺を通って行き来できるというイメージ。

Union-Find木で図1のデータを表現する。

(1)宣言

Union-Find木を宣言する。
「UnionFindTree 名前 = UnionFindTree(要素数);」
で宣言できる。

int N = 8;//要素数
UnionFindTree UFT = UnionFindTree(N);

これでUFTという名前のUnion-Find木を要素数8で宣言できた。

(2)要素同士の結合

図1で繋がっている辺を見て要素同士を結合していく。
「名前.unite(a, b);」で要素aと要素bを結合できる。

UFT.unite(1, 0);
UFT.unite(1, 2);
UFT.unite(1, 3);
UFT.unite(4, 5);
UFT.unite(4, 6);
UFT.unite(5, 6);

これで要素同士をつなぐことができたので図1のデータがUnion-Find木で表現できた。

(3)同じグループであるか判定

「名前.same(a, b)」でaとbが同じグループであるか判定できる。（同じグループならtrue,違うグループならfalseを返す。）

cout << UFT.same(1, 2) << endl;
cout << UFT.same(0, 3) << endl;
cout << UFT.same(2, 4) << endl;

これの出力結果は

1
1
0

である。

1と2は同じグループ
0と3は同じグループ
2と4は違うグループ

ということだ。確かに正しい。

Union-Find木の結合、判定の計算量は要素数をNとすると、O(α(N)) である。
α(N)は、Nのアッカーマン関数の逆関数といい、log(N)よりも小さい。

最短経路問題まとめ

最短経路問題におけるグラフの表現方法、BFS、ダイクストラ法、ベルマンフォード法、ワ―シャルフロイド法についてまとめた。

(1)グラフの表現方法

(1)-[1]重みなしグラフ

重みなしグラフとは、グラフの辺の重みがすべて1のグラフである。

(1)-[1]-<1> 隣接リスト

重みなしグラフは隣接リストを使って表される。
隣接リストとは各頂点についてその頂点に直接つながっている頂点を列挙したものである。
下のグラフについて考える。

グラフ1 : 重みなしグラフ

このグラフを隣接リストで表すと次のようになる。

0 : 3
1 : 2 , 3
2 : 1
3 : 0 , 1 , 4 , 7
4 : 3 , 7
5 : 6
6 : 5
7 : 3 , 4

この隣接リストは次のように2次元配列で表せる。

int V = 8;//頂点数
vector<vector<int>>G(V);//隣接リストを表す2次元配列
G = {   {3},
	{2,3},
	{1},
	{0,1,4,7},
	{3,7},
	{6},
	{5},
	{3,4}   };

G[i]には頂点iに繋がっている頂点が列挙されているとみると、これで隣接リストが表現できたことになる。

競プロの問題で重みなしグラフが与えられるときは、隣接リストが与えられるときもあれば、次のようにつながっている頂点のペアが列挙されて与えられるときもある。

[例]グラフ1

8 7
0 3
1 3
1 2
3 7
3 4
7 4
5 6

1行目の8は頂点数、7は辺の数である。2行目以降は各辺がつなぐ2つの頂点が書かれている。
このような入力から隣接リストを作る方法は以下の通りである。

int V;//頂点数
int E;//辺の数
cin >> V >> E;
vector<vector<int>>G(V);//隣接リスト
for (int i = 0 ; i < E ; i++) {
	int a, b;
	cin >> a >> b;
	G[a].push_back(b);
	G[b].push_back(a);
}

隣接リストはG[i]にiとつながっている頂点が列挙されているので上の方法で隣接リストを作成できた。

(1)-[2] 重み付きグラフ

重み付きグラフとは、辺に重みが付いているグラフのことである。

(1)-[2]-<1> 隣接リスト

重み付きグラフを隣接リストで表すには辺と重みをペアで扱う必要がある。

下のようなグラフを考える。

グラフ2 : 重み付きグラフ

このグラフを隣接リストで表すと次のようになる。

0 : (1,1) , (2,4) , (3,2)
1 : (0,1) , (3,3)
2 : (0,4) , (3,50) , (4,2)
3 : (0,2) , (1,3) , (2,50) , (4,6)
4 : (2,2) , (3,6) , (5,2)
5 : (4,2)
6 : (7,3)
7 : (6,3)

それぞれのかっこの前半は繋がっている頂点、後半は繋げている辺の重みである。

この隣接リストはpairの2次元配列で次のように表せる。

#define mp make_pair

int V = 8;//辺の数
vector<vector<pair<int, int>>>G;//隣接リスト
G = {   {mp(1,1) , mp(2,4) , mp(3,2)},
	{mp(0,1) , mp(3,3)},
	{mp(0,4) , mp(3,50) , mp(4,2)},
	{mp(0,2) , mp(1,3) , mp(2,50) , mp(4,6)},
	{mp(2,2) , mp(3,6) , mp(5,2)},
	{mp(4,2)},
	{mp(7,3)},
	{mp(6,3)}   };

問題で重み付きグラフが与えられるときは次のように与えられることが多い。
[例]グラフ2

8 9
0 1 1
0 3 2
0 2 4
1 3 3
2 3 50
2 4 2
3 4 6
4 5 2
6 7 3

1行目の8は頂点数、9は辺の数である。
2行目からは頂点、その頂点と繋がっている頂点、辺の重みが空白区切りで与えられる。

この入力から隣接リストは次のように作る。

#define mp make_pair

int V;//頂点数
int E;//辺の数
cin >> V >> E;
vector<vector<pair<int, int>>>G(V);//隣接リスト
for (int i = 0; i < E; i++) {
	int a, b, cost;
	cin >> a >> b >> cost;
	G[a].push_back(mp(b, cost));
	G[b].push_back(mp(a, cost));
}

(1)-[2]-<2> 隣接行列

隣接行列はV*Vの行列でグラフを表す方法である。主にワ―シャルフロイド法で用いられる。
隣接行列をGとすると、頂点iと頂点jが繋がっているときG[i][j]を頂点iと頂点jを結ぶ辺の重みに、繋がっていないときはG[i][j]を非常に大きい値しておく。ただしi=jのときはG[i][j]=0にする。

グラフ2を隣接行列で表すと次のようになる。

グラフ2

int INF = 1000000000;
int V = 8;//頂点数
vector<vector<int>>G(V, vector<int>(V));//V*Vの隣接行列
G = {   { 0 , 1 , 4 , 2 ,INF,INF,INF,INF},
	{ 1 , 0 ,INF, 3 ,INF,INF,INF,INF},
	{ 4 ,INF, 0 , 50, 2 ,INF,INF,INF},
	{ 2 , 3 , 50, 0 , 6 ,INF,INF,INF},
	{INF,INF, 2 , 6 , 0 , 2 ,INF,INF},
	{INF,INF,INF,INF, 2 , 0 ,INF,INF},
	{INF,INF,INF,INF,INF,INF, 0 , 3 },
	{INF,INF,INF,INF,INF,INF, 3 , 0 }    };

次のような入力から隣接行列は次のように作る。
[例]グラフ2

8 9
0 1 1
0 3 2
0 2 4
1 3 3
2 3 50
2 4 2
3 4 6
4 5 2
6 7 3

int INF = 1000000000;
int V;//頂点数
int E;//辺の数
cin >> V >> E;
vector<vector<int>>G(V, vector<int>(V,INF));//V*Vの隣接行列。INFで初期化
for (int i = 0; i < V; i++) {
       G[i][i] = 0;
}
for (int i = 0; i < E; i++) {
	int a, b, cost;
	cin >> a >> b >> cost;
	G[a][b] = cost;
	G[b][a] = cost;
}

(2)BFS（幅優先探索）

BFSは重みなしグラフの最短経路を求めるときに使われる。

[例]グラフ1における頂点0から他の各頂点への最短距離を求める。たどりつけない場合はINFにする。

グラフ1 : 重みなしグラフ

int INF = 1000000000;
int V = 8;//頂点数
int E = 7;//辺の数
vector<vector<int>>G(V);//隣接リスト
G = {   {3},
	{2,3},
	{1},
	{0,1,4,7},
	{3,7},
	{6},
	{5},
	{3,4} };
int start = 0;//スタート位置

vector<int>dist(V, INF);//startからの距離を入れる配列。INF(未訪問)で初期化
queue<int> que;

dist[start] = 0;
que.push(start);

//BFS
while (!que.empty()) {
	int v = que.front();
	que.pop();

for (int nv : G[v]) {
		if (dist[nv] != INF)continue;
		dist[nv] = dist[v] + 1;
		que.push(nv);
	}
}

これでdist[i]には頂点0から頂点iまでの最短距離（たどりつけない場合はINF）が入っている。distの中身は{0, 2, 3, 1, 2, INF, INF, 2}になった。
BFSでは1つの頂点からの他の全頂点への最短距離がO(V+E)で求まる。

(3)ダイクストラ法

ダイクストラ法は、負の重みが存在しない重み付きグラフの最短経路を求めるときに使われる。

[例]グラフ2において頂点0から各頂点までの最短経路を求める。たどりつかない場合はINFにする。

グラフ2

#define mp make_pair
#define P pair<int,int>


int INF = 1000000000;

int V = 8;//辺の数
vector<vector<pair<int, int>>>G(V);//隣接リスト
G = {   {mp(1,1) , mp(2,4) , mp(3,2)},
	{mp(0,1) , mp(3,3)},
	{mp(0,4) , mp(3,50) , mp(4,2)},
	{mp(0,2) , mp(1,3) , mp(2,50) , mp(4,6)},
	{mp(2,2) , mp(3,6) , mp(5,2)},
	{mp(4,2)},
	{mp(7,3)},
	{mp(6,3)}   };

int start = 0;//スタート位置
vector<int>dist(V, INF);//startからの距離を入れる配列。INF(未訪問)で初期化
dist[start] = 0;
priority_queue<P, vector<P>, greater<P>>que;//少ない値を優先するプライオリティキューを宣言
que.push(mp(dist[start], start));

while (!que.empty()) {
	P p = que.top();
	int v = p.second;
	que.pop();
	if (dist[v] < p.first)continue;
	for (int i = 0; i < G[v].size(); i++) {
		P e = G[v][i];
		int u = e.first, cst = e.second;
		if (dist[u] > dist[v] + cst) {
			dist[u] = dist[v] + cst;
			que.push(mp(dist[u], u));
		}
	}
}

これでdist[i]に頂点0から頂点iまでの最短距離（たどりつかないときはINF）が入った。
distの中身は{0, 1, 4, 2, 6, 8, INF, INF}になった。

ダイクストラ法では、1つの頂点から他の全頂点までの最短経路を
O(ElogV)で求められる。

(4)ベルマンフォード法

ベルマンフォード法は、負の重みをもつ辺が存在するグラフの最短経路問題で使われる。
下のグラフを考える。

グラフ3 : 負の重みの辺が存在するグラフ

辺が矢印となっているが、これは矢印の方向のみ移動できるということである。このような辺を有向辺という。また、グラフ1、グラフ2のような辺を無向辺という。無向辺は双方向に有向辺が伸びていると考えれば考え方は同じである。
グラフ3の隣接リストは次のようになる。

#define mp make_pair
#define P pair<int,int>


int V = 8;//頂点の数
vector<vector<P>>G(V);
G = {
	{mp(1,1),mp(2,8)},
	{mp(2,2),mp(3,3)},
	{mp(3,-3)},
	{},
	{mp(6,1)},
	{mp(4,-4)},
	{mp(5,2),mp(7,3)},
	{}
};

グラフ3で、頂点4→頂点6→頂点5 の順に周り続ければコストを無限に小さくできる。このような全体の重みが負である閉路のことを負閉路という。負閉路が存在するとおかしくなるのでそのようなときは例外処理をする必要がある。

[例]グラフ3で頂点0から各頂点までの最小コストを求める。

#define mp make_pair
#define P pair<int,int>
#define INF 100000000


struct edge//辺を表す構造体
{
	int from, to;
	int cost;
};

vector<int> bellman_ford(int start, vector<vector<P>>G){
	//startから各点への最短距離を配列で返す
	//辿り着けなかったらINFにする
	//startから負の閉路に到達できたら空の配列を返す
	int V = G.size();
	vector<int>dist(V, INF);
	dist[start] = 0;

	vector<edge> es;
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < G[i].size(); j++) {
			edge tmpes;
			tmpes.from = i;
			tmpes.to = G[i][j].first;
			tmpes.cost = G[i][j].second;
			es.push_back(tmpes);
		}
	}
	bool flag = true;

	for (int i = 0; i < V; i++) {
		for (auto& e : es) {
			if (dist[e.from] < INF && dist[e.from] + e.cost < dist[e.to]) {
				if (i == V - 1) {
					flag = false;
				}
				dist[e.to] = dist[e.from] + e.cost;
			}
		}
	}
	if (flag == true) {
		return dist;
	}
	else {
		dist.clear();
		return dist;
	}
}


int main() {
	int V = 8;//頂点の数
	vector<vector<P>>G(V);
	G = {
		{mp(1,1),mp(2,8)},
		{mp(2,2),mp(3,3)},
		{mp(3,-3)},
		{},
		{mp(6,1)},
		{mp(4,-4)},
		{mp(5,2),mp(7,3)},
		{}
	};

	int start = 0;
	vector<int>dist(V);
	dist = bellman_ford(start, G);
}

これでdist[i]に頂点0から頂点iまでの最小のコストが入った。
今、distの中身は
{0, 1, 3, 0, INF, INF, INF, INF} である。

また、例えばスタート地点を4にすると頂点4から負閉路に到達できるためdistは空の配列になる。

ベルマンフォード法では1つの頂点から他の全頂点までの最短距離（最小コスト）が、O(VE)で求まる。

(5)ワーシャルフロイド法

ワーシャルフロイド法は、全ての2頂点間の最短経路を求めることができる。
隣接行列を用いる。

[例]グラフ2の全ての2頂点間の最短経路を求める。（たどりつけない場合はINFにする。）

int INF = 1000000000;
int V = 8;//頂点数
vector<vector<int>>G(V, vector<int>(V));//V*Vの隣接行列
G = {   { 0 , 1 , 4 , 2 ,INF,INF,INF,INF},
	{ 1 , 0 ,INF, 3 ,INF,INF,INF,INF},
	{ 4 ,INF, 0 , 50, 2 ,INF,INF,INF},
	{ 2 , 3 , 50, 0 , 6 ,INF,INF,INF},
	{INF,INF, 2 , 6 , 0 , 2 ,INF,INF},
	{INF,INF,INF,INF, 2 , 0 ,INF,INF},
	{INF,INF,INF,INF,INF,INF, 0 , 3 },
	{INF,INF,INF,INF,INF,INF, 3 , 0 }   };
	
//ワーシャルフロイド
for (int k = 0; k < V; k++) {
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
		}
	}
}

こうするとGは

0 1 4 2 6 8 INF INF
1 0 5 3 7 9 INF INF
4 5 0 6 2 4 INF INF
2 3 6 0 6 8 INF INF
6 7 2 6 0 2 INF INF
8 9 4 8 2 0 INF INF
INF INF INF INF INF INF 0 3
INF INF INF INF INF INF 3 0

となり、G[i][j]が頂点iと頂点jの最短経路を表している。

ワーシャルフロイド法は全ての2頂点間の最短経路を
O(V*V*V)で求めることができる。

また、ワーシャルフロイド法は、負の重みの辺がある場合にも使える。負の閉路がある場合にはG[i][j](i=j)の値が負になるので負の閉路の判定もできる。
負の経路があるときワーシャルフロイド法ではINFの値が変えられる可能性があるため注意が必要である。（INFの判定をINFより少し小さい値で行うなど。）