探索系

二分グラフ判定

int n;
vector<int>G[210];
int color[210]; //頂点iの色(1 or -1)
//二分グラフ判定

bool dfs(int v,int c) {
	color[v] = c;//頂点vをcで塗る
	for (int i = 0; i < G[v].size(); ++i) {
		//隣接している頂点が同じ色ならfalse
		if (color[G[v][i]] == c)return false;
		if (color[G[v][i]] == 0 && !dfs(G[v][i], -c))return false;
	}
	return true;
}

幅優先探索はこんな感じでした

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int main() {
    int R, C;
    int sy, sx, gy, gx;
    cin >> R >> C;
    cin >> sy >> sx >> gy >> gx;
    sy--; sx--; gx--; gy--;
    char c[51][51];
    int d[51][51];
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> c[i][j];
            d[i][j] = INF;
        }
    }
    int dx[4] = { 1,0,-1,0 };
    int dy[4] = { 0,1,0,-1 };
    queue<pii>Q;
    Q.push({ sy,sx });
    d[sy][sx] = 0;
    while (!Q.empty()) {
        int y = Q.front().first;
        int x = Q.front().second;
        Q.pop();
        for (int i = 0; i < 4; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (0 <= ny && ny < R && 0 <= nx && nx < C&&c[ny][nx] == '.'&&d[ny][nx]==INF){
                Q.push({ ny,nx });
                d[ny][nx] = d[y][x] + 1;
            }
        }
    }
    cout << d[gy][gx] << endl;
    return 0;
}

双方向幅優先探索

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#define _USE_MATH_DEFINES
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
double mysqrt(double x) {
	double l = 0, r = x;
	for (int i = 0; i < 64; ++i) {
		double m = (l + r) / 2.0;
		if (m*m < x)l = m;
		else r = m;
	}
	return l;
}
///////////////////////////////////////

int main() {
	int R, C;
	int sy, sx, gy, gx;
	cin >> R >> C;
	cin >> sy >> sx >> gy >> gx;
	sy--, sx--, gy--, gx--;
	char c[51][51];
	int d[51][51];
	int d2[51][51];
	for (int i = 0; i < R; ++i) {
		for (int j = 0; j < C; ++j) {
			cin >> c[i][j];
			d[i][j] = INF;
			d2[i][j] = INF;
		}
	}
	queue<pair<pii,int>>Q;
	Q.push({ { sy,sx },0 });
	Q.push({ { gy,gx },1 });
	d[sy][sx] = 0;
	d2[gy][gx] = 0;
	while (!Q.empty()) {
		int y = Q.front().first.first;
		int x = Q.front().first.second;
		int k = Q.front().second;
		Q.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (c[ny][nx] == '#')continue;
			if (d[ny][nx] == INF && d2[ny][nx] != INF&&k==0) {
				cout << d[y][x] + d2[ny][nx]+1 << endl;
				return 0;
			}
			else if (d2[ny][nx] == INF && d[ny][nx] != INF&&k==1) {
				cout << d2[y][x] + d[ny][nx]+1 << endl;
				return 0;
			}
			else if (d[ny][nx]==INF&&k==0) {
				Q.push({{ ny,nx }, k});
				d[ny][nx] = d[y][x] + 1;
			}
			else if (d2[ny][nx]==INF&&k == 1) {
				Q.push({ { ny,nx }, k });
				d2[ny][nx] = d2[y][x] + 1;
			}
		}
	}
	
	return 0;
}

01BFS ARC005 C

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int main() {
	int H, W;
	cin >> H >> W;
	string C[500];
	for (int i = 0; i < H; ++i) {
		cin >> C[i];
	}
	//スタートとゴールを探す
	int si, sj, gi, gj;
	for (int i = 0; i < H; ++i) {
		int j = C[i].find('s');
		if (j >= 0) {
			si = i;
			sj = j;
		}
		j = C[i].find('g');
		if (j >= 0) {
			gi = i;
			gj = j;
		}
	}

	//距離=壁マスを通る回数として最短路問題を解く
	int dist[500][500];
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			dist[i][j] = 1e9;
			dist[si][sj] = 0;
		}
	}
	//dequeを使って01-BFS
	deque<pair<int, int>>que;
	que.push_back({ si,sj });
	while (que.size()) {
		auto p = que.front(); que.pop_front();
		int i = p.first, j = p.second;
		//4方向の遷移
		for (int k = 0; k < 4; ++k) {
			int i2 = i + dy[k], j2 = j + dx[k];
			if (i2 < 0 || i2 >= H || j2 < 0 || j2 >= W)continue;
			bool wall = (C[i][j] == '#');
			int d2 = dist[i][j] + wall;
			//暫定距離より短い経路がえられた場合は更新して+1なら後ろに+0なら前につける
			if (dist[i2][j2] > d2) {
				dist[i2][j2] = d2;
				if (wall) {
					que.push_back({ i2,j2 });
				}
				else {
					que.push_front({ i2,j2 });
				}
			}
		}
	}
	//終点までの距離が2以下ならYES
	cout << (dist[gi][gj] <= 2 ? "YES" : "NO") << endl;
	return 0;
}

これはダイクストラでも解ける

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
struct edge { int to, cost; };
vector<edge>G[110];
int H, W;
char C[510][510];
int dis[510][510];
void dijkstra(pii s) {
	priority_queue<pair<int,pii>, vector<pair<int,pii>>,greater<pair<int,pii>>>que;
	for (int i = 0; i < 510; ++i) {
		for (int j = 0; j < 510; ++j) {
			dis[i][j] = INF;
		}
	}
	dis[s.first][s.second]= 0;
	que.push({ 0,s });
	while (!que.empty()) {
		int c = que.top().first;
		pii v = que.top().second;
		que.pop();
		if (dis[v.first][v.second] < c)continue;
		for (int i = 0; i < 4; ++i) {
			int ny = v.first + dy[i];
			int nx = v.second + dx[i];
			if (ny < 0 || ny >= H || nx < 0 || nx >= W || dis[ny][nx] != INF) {
				continue;
			}
			int plus;
			if (C[ny][nx] == '#') {
				plus = 1;
			}
			else {
				plus = 0;
			}
			int cost = dis[v.first][v.second] + plus;
			if (dis[ny][nx] > dis[v.first][v.second]) {
				dis[ny][nx] = cost;
				que.push({ cost,{ny,nx} });
			}
		}
	}
}
int main() {
	cin >> H >> W;
	pii st, go;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cin >> C[i][j];
			if (C[i][j] == 's') {
				st = { i,j };
			}
			else if (C[i][j] == 'g') {
				go = { i,j };
			}
		}
	}
	dijkstra(st);
	if (dis[go.first][go.second]<=2) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}

AGC 033 A
darker and darker

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int main() {
	int H, W; cin >> H >> W;
	char A[1010][1010];
	queue <pair<pii,int>>Q;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cin >> A[i][j];
			if (A[i][j] == '#') {
				Q.push({ {i,j},0 });
			}
		}
	}
	int ans = 0;
	while (!Q.empty()) {
		auto key = Q.front();
		ans = max(ans, key.second);
		Q.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = key.first.first + dy[i];
			int nx = key.first.second + dx[i];
			if (ny < 0 || ny >= H || nx < 0 || nx >= W||A[ny][nx]=='#') {
				continue;
			}
			else {
				A[ny][nx] = '#';
				Q.push({ { ny,nx }, key.second + 1 });
			}
		}
	}
	cout << ans << endl;
	return 0;
}

深さ優先探索
高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。

高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
void search(int x, int y);
int W, H;
char G[510][510];
bool visited[510][510];
int main() {
	int sy, sx;
	int gy, gx;
	cin >> H >> W;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cin >> G[i][j];
			if (G[i][j] == 's') {
				sy = i; sx = j;
			}
			if (G[i][j] == 'g') {
				gy = i; gx = j;
			}
		}
	}
	search(sx, sy);
	if (visited[gy][gx]) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
    return 0;
}

void search(int x, int y) {
	if (x < 0 || W <= x || y < 0 || H <= y)return;
	if (G[y][x] == '#')return;
	if (visited[y][x])return;
	visited[y][x] = true;
	search(x + 1, y);
	search(x - 1, y);
	search(x, y + 1);
	search(x, y - 1);
}

こういう風に書くのか

二部グラフ判定のようなもの
maximum-cup C 嘘つきな天使
https://atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_c

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
vector<bool>visited(100100, false);
vector<int>target(100100);
int judge(int i, int n) {
	visited[i] = true;
	if (!visited[target[i]]) {
		return judge(target[i], n + 1);
	}
	else {
		return n + 1;
	}
}
int main() {
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int A;
		cin >> A;
		A--;
		target[i] = A;
	}
	for (int i = 0; i < N; ++i) {
		if (!visited[i]) {
			int num = judge(i, 0);
			if (num % 2 > 0) {
				cout << -1 << endl;
				return 0;
			}
		}
	}
	cout << N / 2 << endl;
	return 0;
}

応用
ARC31-B

とある所に島国がありました。島国にはいくつかの島があります。このたび、この島国で埋め立て計画が立案されたのですが、どこを埋め立てるか決まっていません。できることなら埋め立てによって島を繋いで、1つの島にしてしまいたいのですが、たくさん埋め立てるわけにもいきません。10マス × 10マスのこの島国の地図が与えられるので、1マスを埋め立てた時に 1つの島にできるか判定してください。ただし、地図で陸地を表すマスが上下左右につながっている領域のことを島と呼びます。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };

char ma[11][11];
int used[11][11];
void dfs(int y, int x) {
	if (x < 0 || 9 < x || y < 0 || 9 < y)return;
	if (used[y][x])return;
	if (ma[y][x] == 'x')return;
	used[y][x] = 1;
	for (int i = 0; i < 4; ++i) {
		dfs(y + dy[i], x + dx[i]);
	}
}//'o'があるところと繋がっているところだけusedを1にしていく
int main() {
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 10; ++j) {
			cin >> ma[i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 10; ++j) {
			fill_n(*used,11*11,0);
			int f = (ma[i][j] == 'x');
			ma[i][j] = 'o';
			dfs(i, j);
			if (f)ma[i][j]='x';//修正
			int tsk = 1;
			for (int y = 0; y < 10; ++y) {
				for (int x = 0; x < 10; ++x) {
					if (ma[y][x] == 'o'&&used[y][x] == 0) {
						tsk = 0;
					}
				}
			}
			if (tsk)ans = 1;
		}
	}
	if (ans)cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

union-find
1,vectorpar;
par[a]=bとなると、aの親がbである、という意味。
3-2-1という木の場合3の親は2であるためpar[3]=2である。
2,union-find(int N):
1で述べたparの定義に基づくとpar[i]=iの時[iの親はi]であるからこのiは木の根に相当する箇所であるすなわちこの関数では最初は全て根であるとして初期化する
3, int root(int x):
データxが木の根の場合はx(根)ｗｐ返す
データxが木の根でない場合はparで親を再帰的にたぐり最終的に親のおおもとを返す
すなわちこの関数はxの根を返す関数である
4,void unite(int x,int y):
xの根である所のrxとyの根である所のryが同じならばそのまま、同じ出ない時はxの根ryをyの根ryにつける。すなわちこの関数は根が同じでない二つの木を併合する関数である
5,bool same(int x,int y):
2つのデータx,yが属する木が同じならtrueを返す関数である。

class UnionFind {
	vector<int>par;

	UnionFind(int N) :par(N) {
		for (int i = 0; i < N; ++i) {
			par[i] = i;
		}
	}

	int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;
		par[rx] = ry;
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

rankのある番は

struct UnionFind {
	vector<int>par;
	vector<int>rank;

	UnionFind(int N) :par(N),rank(N) {
		for (int i = 0; i < N; ++i) {
			par[i] = i;
			rank[i] = 0;
		}
	}

	int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;//各木について木の高さ(rank)を記憶しておく
		if (rank[x] < rank[y]) {
			//併合の際に二つの木のrankが異なればrankの小さいものから大きいものへ辺を張る
			par[rx] = ry;
		}
		else {
			par[ry] = rx;
			if (rank[rx] == rank[ry])rank[rx]++;
		}
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

蟻本　食物連鎖
N匹の動物がいて1,2,,,Nと番号が付けられています動物は全て３つの種類A,B,Cのいずれかです。AはBを食べBはCを食べます次の２種類の情報が順番にk個与えられます
タイプ1:xとyは同じ種類です
タイプ2:xはyを食べます
これらは全て正しいとは限りません以前に与えられた情報と矛盾する情報やx,yが正しい番号(1,2,,,N)でないような正しくない情報が与えられる可能性があります。K個の情報のうちそのような情報の個数を出力してください
各動物Iについて３つの要素i-A,i-B,i-Cを作り3*N個の要素でのUnion-Findを作ります。このUnion-Findを次のようなものと考えます。
・I-xはIが種類xである場合を表す
・各グループはそれらが全て同時に起こることがわかっていることを表す
例えばI-Aとj-Bが同じグループである場合Iが種類Aならばjは必ず種類Bでありjが種類BならばIは必ず種類Aであることを表しています

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
struct UnionFind {
	vector<int>par;
	vector<int>rank;

	UnionFind(int N) :par(N) {
		for (int i = 0; i < N; ++i) {
			par[i] = i;
			rank[i] = 0;
		}
	}

	int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;//各木について木の高さ(rank)を記憶しておく
		if (rank[x] < rank[y]) {
			//併合の際に二つの木のrankが異なればrankの小さいものから大きいものへ辺を張る
			par[x] = y;
		}
		else {
			par[y] = x;
			if (rank[x] == rank[y])rank[x]++;
		}
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
int main() {
	int N, K;
	int T[100100], X[100100], Y[100100];
	cin >> N >> K;
	for (int i = 0; i < K; ++i) {
		cin >> T[i] >> X[i] >> Y[i];
	}
	UnionFind tree(N*3);
	int ans = 0;
	for (int i = 0; i < K; ++i) {
		int t = T[i];
		int x = X[i] - 1;int y = Y[i] - 1;//0,...,N-1の範囲にする
		if (x < 0 || N <= x || y < 0 || N <= y) {
			ans++;
			continue;
		}
		if (t == 1) {
			if ( tree.same(x, y + N) || tree.same(x, y + 2 * N)) {
				ans++;
			}
			else {
				tree.unite(x, y);
				tree.unite(x + N, y + N);
				tree.unite(x + 2 * N, y + 2 * N);
			}
		}
		else {
			if (tree.same(x, y) || tree.same(x, y + 2 * N)) {
				ans++;
			}
			else {
				tree.unite(x, y + N);
				tree.unite(x + N, y + 2 * N);
				tree.unite(x + 2 * N, y);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

例題1,ABC097 D;
1からNまでの整数を並び替えた順列p1,p2,,,,pNがあります。また、１以上N以下の整数のペアがM個与えられます。これらは(x1,y1),,,,(xM,yM)で表される。シカのAtCoDeerくんは順列pに次の操作を好きなだけ行ってpi=iとなるiの数を最大にしようと考えています。・1<=j<=Mなるjを選びpxj,pyjをスワップする
操作後のpi=iとなるiの数として考えうる最大値を求めてください

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
struct UnionFind {
	vector<int>par;

	UnionFind(int N) :par(N) {
		for (int i = 0; i < N; ++i) {
			par[i] = i;
		}
	}

	int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;
		par[rx] = ry;
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
int main(){
	int N, M;
	cin >> N >> M;
	vector<int>P(N);
	for (int i = 0; i < N; ++i) {
		cin >> P[i];
	}
	UnionFind tree(N);
	for (int i = 0; i < M; ++i) {
		int x, y;
		cin >> x >> y;
		tree.unite(x - 1, y - 1);
	}
	int cnt = 0;
	for (int i = 0; i < N; ++i) {
		if (tree.same(i, P[i] - 1)) {
			cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}

例題,ATC
N 頂点の、単純とは限らない無向グラフを考えます。 初期状態では、頂点のみが存在し、辺は全く存在せず、全ての頂点が孤立しているとします。 以下の 2 種類のクエリが、Q 回与えられます。
連結クエリ： 頂点 A と、頂点 B を繋ぐ辺を追加します。
判定クエリ： 頂点 A と、頂点 B が、連結であるかどうか判定します。連結であれば Yes、そうでなければ No を出力します。
クエリを順番に処理し、判定クエリへの回答を出力して下さい。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
struct UnionFind {
	vector<int>par;

	UnionFind(int N) :par(N) {
		for (int i = 0; i < N; ++i) {
			par[i] = i;
		}
	}

	int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;
		par[rx] = ry;
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
int main(){
	int N, Q;
	cin >> N >> Q;
	UnionFind tree(N);
	for (int i = 0; i < Q; ++i) {
		int p, x, y;
		cin >> p >> x >> y;
		if (p == 0) {
			tree.unite(x, y);
		}
		else {
			if (tree.same(x, y)) {
				cout << "Yes" << endl;
			}
			else {
				cout << "No" << endl;
			}
		}
	}
	return 0;
}

バウムテスト

ARC37-B
バウムテストとは、被験者に「木」の絵を描かせることで被験者の心理状態を読み取る心理検査である。この検査を受けた高橋君は、 N 個の頂点と M 本の辺からなる無向グラフを描いた。このグラフの連結成分のうち木であるようなもの、すなわち閉路を持たないものの個数を求めよ。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
struct UnionFind {
	vector<int>par;

	UnionFind(int N) :par(N) {
		for (int i = 0; i < N; ++i) {
			par[i] = i;
		}
	}
	int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;
		par[rx] = ry;
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
int N, M;
vector<int>G[110];
bool memo[110];
bool flag;
void def(int a,int b) {
	memo[a] = true;
	for (auto i : G[a]) {
		if (i == b)continue;
		if (memo[i]) {
			flag = false;
		}
		else {
			def(i, a);
		}
	}
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for (int i = 0; i < 110; ++i) {
		memo[i] = false;
	}
	int res = 0;
	for (int i = 0; i < N; ++i) {
		if (!memo[i]) {
			flag = true;
			def(i, -1);
			if (flag) {
				res++;
			}
		}
	}
	cout << res << endl;
	return 0;
}

abc120-D

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
struct UnionFind {
	vector<int>par;
	UnionFind(int n):par(n,-1){}
	void init(int n) { par.assign(n, -1); }

	int root(int x) {
		if (par[x] < 0)return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y) {
		return root(x) == root(y);
	}

	bool merge(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y)return false;
		if (par[x] > par[y])swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x) {
		return -par[root(x)];
	}
};
int main() {
	ll N, M; cin >> N >> M;
	vector<int>A(M), B(M);
	for (int i = 0; i < M; ++i) {
		cin >> A[i] >> B[i], --A[i], --B[i];
	}
	UnionFind uf(N);
	ll cur = N * (N - 1) / 2;
	vector<ll>res;
	for (int i = 0; i < M; ++i) {
		res.push_back(cur);
		int a = A[M - 1 - i], b = B[M - 1 - i];
		if (uf.issame(a, b))continue;

		ll sa = uf.size(a), sb = uf.size(b);
		cur -= sa * sb;
		uf.merge(a, b);
	}
	reverse(res.begin(), res.end());
	for (int i = 0; i < res.size(); ++i) {
		cout << res[i] << endl;
	}
	return 0;
}

abc120 d

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
struct UnionFind {
	vector<int>par;
	UnionFind(int n) :par(n,-1) {}
	void init(int n) { par.assign(n, -1); }
	
	int root(int x) {
		if (par[x] < 0)return x;
		return par[x] = root(par[x]);
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}

	bool merge(int x, int y) {
		x = root(x); y = root(y);
		if (x == y)return false;
		if (par[x] > par[y])swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x) {
		return -par[root(x)];
	}
};
int main() {
	ll N, M; cin >> N >> M;
	vector<int>A(M), B(M);
	for (int i = 0; i < M; ++i) {
		cin >> A[i] >> B[i];
		--A[i], --B[i];
	}
	UnionFind uf(N);
	ll cur = N * (N - 1) / 2;
	vector<ll>res;
	for (int i = 0; i < M; ++i) {
		res.push_back(cur);
		int a = A[M-1-i], b = B[M-1-i];
		if (uf.same(a, b))continue;
		ll sa = uf.size(a), sb = uf.size(b);
		cur -= sa * sb;
		uf.merge(a, b);
	}
	reverse(res.begin(), res.end());
	for (int i = 0; i < res.size(); ++i) {
		cout << res[i] << endl;
	}
	return 0;
}

アリ本　lake counting

Lake Counting
大きさがＮ×Ｍの庭があります。そこに雨が降り、水たまりができました。水たまりは８近傍で隣接している場合に繋がっているとみなします。全部でいくつの水たまりがあるでしょうか。
N,M<=100;

方針
適当なＷから始め、そこから繋がっている部分を．に置き換えるという操作を繰り返していきます。１回のＤＦＳで、はじめのＷとつながっているＷは全部．に置き換わるので、Ｗがなくなるまでに何回ＤＦＳを行ったかが答えになります。状態の遷移は８方向の移動の８通りで、ＤＦＳは各マスに対してたかだか１回しか呼ばれないので計算量はＯ(8NM)となります。

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int N,M;
char field[110][110];
void dfs(int x, int y) {
    field[x][y] = '.';
    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            int nx = x + dx, ny = y + dy;
            if (0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W')
                dfs(nx, ny);
        }
    }
    return;
}
int main() {
    int res = 0;
    cin >> N >> M;
    char tmp;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
                        cin >> tmp
            field[i][j] = tmp;
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (field[i][j] == 'W') {
                dfs(i, j);
                res++;
            }
        }
    }
    cout << res;
}

ABC 088 grid repainting

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
int main() {
	int H, W;
	cin >> H >> W;
	char G[51][51];
	int d[51][51];
	int count = 0;//'.'の数
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cin >> G[i][j];
			d[i][j] = INF;
			if (G[i][j] == '.')count++;
		}
	}
	queue<pii>Q;
	d[0][0] = 0;
	Q.push({ 0,0 });
	while (!Q.empty()) {
		int y = Q.front().first;
		int x = Q.front().second;
		Q.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (0 <= ny && ny < H && 0 <= nx && nx < W&&G[ny][nx] == '.'&&d[ny][nx] == INF) {
				Q.push({ ny,nx });
				d[ny][nx] = d[y][x] + 1;
			}
		}
	}
	if (d[H - 1][W - 1] == INF)cout << -1 << endl;
	else {
		cout << count - d[H - 1][W - 1] - 1 << endl;
	}
	return 0;
}

ABC 054 C one-stroke path

 #include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
int N, M;
vector<int>G[10];
vector<bool>visited(10, false);
int ans = 0;
int cnt = 0;
int dfs(int now,int cnt) {
	if (visited[now])return 0;
	if (cnt == N - 1)return 1;
	visited[now] = true;
	int ans = 0;
	for (int a : G[now]) {
		ans += dfs(a, cnt + 1);
	}
	visited[now] = false;
	return ans;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	cout << dfs(0,0) << endl;
	return 0;
}

ABC 087D people on a line

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
const int MC = 100010;
int N, M;
vector<vector<pii>>V(MC, vector<pii>());
bool b[MC];
int x[MC];
bool dfs(int q) {
	b[q] = 1;
	for (auto u : V[q]) {
		if (b[u.first]) {
			if (x[u.first] != x[q] + u.second)return 0;
			continue;
		}
		else {
			x[u.first] = x[q] + u.second;
			if (!dfs(u.first)) {
				return 0;
			}
		}
	}
	return 1;
}
int main() {
	cin >> N >> M;
	memset(x, 0, sizeof(x));
	for (int i = 0; i < M; ++i) {
		int l, r, d;
		cin >> l >> r >> d;
		V[l].push_back(make_pair(r, d));
		V[r].push_back(make_pair(l, -d));
	}
	for (int i = 1; i <= N; ++i) {
		if (b[i])continue;
		if (!dfs(i)) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

126 D 初めての木

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
///////////////////////////////////////
int N;
vector<vector<pii>>G;
vector<int>res;
//vをcに塗るpはvの親
void dfs(int v, int p, int c) {
	res[v] = c;
	for (auto e: G[v]) {
		if (e.first == p) {
			continue;
		}
		if (e.second & 1) {
			dfs(e.first, v, 1 - c);
		}
		else {
			dfs(e.first, v, c);
		}
	}
}
int main() {
	cin >> N;
	G.assign(N, vector<pii>());
	for (int i = 0; i < N - 1; ++i) {
		int u, v, w; cin >> u >> v >> w;
		--u, --v;
		G[u].push_back({ v,w });
		G[v].push_back({ u,w });
	}
	res.assign(N,0);
	dfs(0, -1, 1);
	for (auto v : res) {
		cout << v << endl;
	}
	return 0;
}

abc070 D transit tree path
幅優先探索と深さ優先探索を木でやる

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
///////////////////////////////////////
int N, Q, K;
vector<pair<int,ll>>G[100100];
int main() {
	cin >> N;
	for (int i = 0; i < N-1; ++i) {
		int a, b; ll c;
		cin >> a >> b >> c;
		a--, b--;
		G[a].push_back({ b,c });
		G[b].push_back({ a,c });
	}
	cin >> Q >> K;
	K--;
	vector<ll>d(N + 1,-1);
	d[K] = 0;
	queue<int>q;
	q.push(K);
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (auto p : G[v]) {
			int sv;
			ll c;
			sv = p.first;
			c = p.second;
			if (d[sv] < 0) {
				d[sv] = d[v] + c;
				q.push(sv);
			}
		}
	}
	for (int i = 0; i < Q; ++i) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		cout << d[x] + d[y] << endl;
	}
	return 0;
}

dfs ver

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
///////////////////////////////////////
int N, Q, K;
vector<pair<int,ll>>G[100100];
ll d[100100];
vector<bool>visited(100100, false);
void dfs(int a,ll c) {
	d[a] = c;
	visited[a] = true;
	for (auto i : G[a]) {
		if (!visited[i.first]) {
			dfs(i.first, c + i.second);
		}
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N-1; ++i) {
		int a, b; ll c;
		cin >> a >> b >> c;
		a--, b--;
		G[a].push_back({ b,c });
		G[b].push_back({ a,c });
	}
	cin >> Q >> K;
	K--;
	dfs(K, 0);
	for (int i = 0; i < Q; ++i) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		cout << d[x]+d[y] << endl;
	}
	return 0;
}

サイズ付きunionfind

struct UnionFind {
	vector<int>par;
	vector<int>sizes;
	UnionFind(int n) :par(n), sizes(n, 1) {
		for (int i = 0; i < n; ++i) {
			par[i] = i;
		}
	}

	int root(int x) {
		if (x == par[x])return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y)return;
		if (sizes[x] < sizes[y]) {
			swap(x, y);
		}
		par[y] = x;
		sizes[x] += sizes[y];
	}

	bool same(int x, int y) {
		return root(x) == root(y);
	}

	int size(int x) {
		return sizes[root(x)];
	}
};

priority_queue ダイクストラ
abc 35 トレジャーハント

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
struct edge { ll to, cost; };
int main() {
	ll N, M, T; cin >> N >> M >> T;
	vector<ll>A(N);
	for (int i = 0; i < N; ++i)cin >> A[i];
	vector<vector<pair<ll,ll>>>tpath(N), bpath(N);
	for (int i = 0; i < M; ++i) {
		ll a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		tpath[a].push_back({ b,c });
		bpath[b].push_back({ a,c });
	}
	vector<ll>tdis(N + 1, 1LL<<50), bdis(N + 1, 1LL<<50);
	//頂点0からの距離
	tdis[0] = 0;
	bdis[0] = 0;
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>tque, bque;
	//firstは1からの距離secondはどこまで
	tque.push({ 0,0 });
	while (!tque.empty()) {
		pair<ll,ll> p = tque.top();
		tque.pop();
		ll v = p.second;
		if (tdis[v] < p.first)continue;
		for (int i = 0; i < tpath[v].size(); ++i) {
			edge e = { tpath[v][i].first,tpath[v][i].second };
			if (tdis[e.to] > tdis[v] + e.cost) {
				tdis[e.to] = tdis[v] + e.cost;
				tque.push({ tdis[e.to],e.to });
			}
		}
	}
	bque.push({ 0,0 });
	while (!bque.empty()) {
		pair<ll,ll> p = bque.top();
		bque.pop();
		ll v = p.second;
		if (bdis[v] < p.first)continue;
		for (int i = 0; i < bpath[v].size(); ++i) {
			edge e = { bpath[v][i].first,bpath[v][i].second };
			if (bdis[e.to] > bdis[v] + e.cost) {
				bdis[e.to] = bdis[v] + e.cost;
				bque.push({ bdis[e.to],e.to });
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i < N; ++i) {
		if (tdis[i] + bdis[i] <= T) {
			ans = max(ans, A[i] * (T - tdis[i] - bdis[i]));
		}
	}
	cout << ans << endl;
	return 0;
}

経路復元

int pre[110];//最短路の直前の頂点
void dijkstra(int a) {
	priority_queue<pii, vector<pii>, greater<pii>>que;
	REP(i, 110)d[i] = INF;
	REP(i, 110)pre[i] = -1;
	d[a] = 0;
	que.push({ 0,a });
	while (!que.empty()) {
		pii P = que.top();
		que.pop();
		int v = P.second;
		if (d[v] < P.first)continue;
		for (int i = 0; i < G[v].size(); ++i) {
			pii e = G[v][i];
			if (d[e.first] > d[v] + e.second) {
				d[e.first] = d[v] + e.second;
				pre[e.first] = v;
				que.push({ d[e.first],e.first });
			}
		}
	}
}
//頂点tへの最短路
vector<int>get_path(int t) {
	vector<int>path;
	for (; t != -1; t = pre[t]) {
		path.push_back(t);
	}
	return path;
}

ダイクストラ例題他
https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/5809263

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
struct edge { ll to, cost; };
int main() {
	ll n, m, s, t;
	cin >> n >> m >> s >> t;
	s--, t--;
	ll u[100100], v[100100], a[100100], b[100100];
	vector<vector<pair<ll, ll>>>ypath(n), spath(n);
	for (int i = 0; i < m; ++i) {
		cin >> u[i] >> v[i] >> a[i] >> b[i];
		u[i]--, v[i]--;
		ypath[u[i]].push_back({ v[i],a[i] });
		ypath[v[i]].push_back({ u[i],a[i] });
		spath[u[i]].push_back({ v[i],b[i] });
		spath[v[i]].push_back({ u[i],b[i] });
	}
	vector<ll>ydis(n + 1, 1LL << 50), sdis(n + 1, 1LL << 50);
	ydis[s] = 0;
	sdis[t] = 0;
	priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>>yen, snuuk;
	yen.push({ 0,s });
	snuuk.push({ 0,s });
	while (!yen.empty()) {
		pair<ll, ll> p = yen.top();
		yen.pop();
		ll v = p.second;
		if (ydis[v] < p.first)continue;
		for (int i = 0; i < ypath[v].size(); ++i) {
			edge e = { ypath[v][i].first,ypath[v][i].second };
			if (ydis[e.to] > ydis[v] + e.cost) {
				ydis[e.to] = ydis[v] + e.cost;
				yen.push({ ydis[e.to],e.to });
			}
		}
	}
	snuuk.push({ 0,t });
	while (!snuuk.empty()) {
		pair<ll, ll>p = snuuk.top();
		snuuk.pop();
		ll v = p.second;
		if (sdis[v] < p.first)continue;
		for (int i = 0; i < spath[v].size(); ++i) {
			edge e = { spath[v][i].first,spath[v][i].second };
			if (sdis[e.to] > sdis[v] + e.cost) {
				sdis[e.to] = sdis[v] + e.cost;
				snuuk.push({ sdis[e.to],e.to });
			}
		}
	}
	vector<ll>ans(n + 1, 1e15);
	for (int i = n-1; i >=0; --i) {
		ans[i] = min(ans[i + 1], ydis[i] + sdis[i]);
	}
	ll tmp = 1e15;
	for (int i = 0; i < n; ++i) {
		cout << tmp-ans[i] << endl;
	}
	return 0;
}

wupc2012 会場への道
拡張ダイクストラ

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
struct edge { int to, cost; };
int n, V;
vector<edge>G[10010];
int d[4][7][10010];
void dijkstra(int s) {
	priority_queue<pii, vector<pii>, greater<pii>>que;
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 7; ++j) {
			for (int k = 0; k < n; ++k) {
				d[i][j][k] = INF;
			}
		}
	}
	d[0][0][s] = 0;
	que.push({ 0,s });
	while (!que.empty()) {
		int c = que.top().first;
		int v = que.top().second;
		que.pop();
		if (d[c % 4][c % 7][v] < c)continue;
		if (v == n - 1)continue;
		for (int i = 0; i < G[v].size(); ++i) {
			edge e = G[v][i];
			int cost = d[c % 4][c % 7][v] + e.cost;
			if (d[cost % 4][cost % 7][e.to] > cost) {
				d[cost % 4][cost % 7][e.to] = cost;
				que.push({ cost,e.to });
			}
		}
	}
}
int main() {
	cin >> n >> V;
	for (int i = 0; i < V; ++i) {
		int f, t, c;
		cin >> f >> t >> c;
		edge e;
		e.to = t, e.cost = c;
		G[f].push_back(e);
		e.to = f;
		G[t].push_back(e);
	}
	dijkstra(0);
	int ans = INF;
	for (int i = 0; i < 4; ++i)ans = min(ans, d[i][0][n - 1]);
	for (int i = 0; i < 7; ++i)ans = min(ans, d[0][i][n - 1]);
	cout << ans << endl;
	return 0;
}

icpc 2008 D

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#define _USE_MATH_DEFINES
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0,1,0,-1};
const ll dy[4] = { -1, 0, 1,0};
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
double mysqrt(double x) {
	double l = 0, r = x;
	for (int i = 0; i < 64; ++i) {
		double m = (l + r) / 2.0;
		if (m*m < x)l = m;
		else r = m;
	}
	return l;
}
///////////////////////////////////////

int main() {
	int w, h; cin >> w >> h;
	int s[31][31];
	int dp[31][31][4];
	int c[4];
	memset(dp, INF, sizeof(dp));
	dp[0][0][1] = 0;
	//dp[y][x][向いている方向]=最小コスト
	//上を0,右を1,下を2,左を3として回転方向を直進+0,+1,+2,+3
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			cin >> s[i][j];
		}
	}
	for (int i = 0; i < 4; ++i) {
		cin >> c[i];
	}
	priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>,greater<tuple<int, int, int, int>>>Q;
	Q.push({ 0,0,0,1 });
	while (!Q.empty()) {
		auto p = Q.top();
		Q.pop();
		int cost = get<0>(p);
		int y = get<1>(p);
		int x = get<2>(p);
		int dir = get<3>(p);//もともと向いている方向
		if (cost > dp[y][x][dir])continue;
		//回転方向
		for (int i = 0; i < 4; ++i) {
			int to_dir = (dir + i) % 4;
			int to_cost = cost;
			if (s[y][x] != i)to_cost += c[i];
			int to_y = y + dy[to_dir];
			int to_x = x + dx[to_dir];
			if (to_y < 0 || to_y >= h || to_x < 0 || to_x >= w)continue;
			if (dp[to_y][to_x][to_dir] > to_cost) {
				dp[to_y][to_x][to_dir] = to_cost;
				Q.push(make_tuple(to_cost, to_y, to_x, to_dir));
			}
		}
	}
	int ans = INF;
	for (int i = 0; i < 4; ++i) {
		ans = min(ans, dp[h - 1][w - 1][i]);
	}
	cout << ans << endl;
	return 0;
}

拡張bfs abc132 E

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#define _USE_MATH_DEFINES
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0,1,0,-1 };
const ll dy[4] = { -1, 0, 1,0 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
double mysqrt(double x) {
	double l = 0, r = x;
	for (int i = 0; i < 64; ++i) {
		double m = (l + r) / 2.0;
		if (m*m < x)l = m;
		else r = m;
	}
	return l;
}
///////////////////////////////////////
struct edge { int to, cost; };
using Graph = vector<vector<int>>;
ll dist[100100][3];
int main() {
	int N, M; cin >> N >> M;
	Graph G;
	G.assign(N, vector<int>());
	int s, t;
	for (int i = 0; i < M; ++i) {
		int u, v; cin >> u >> v;
		--u, --v;
		G[u].push_back(v);
	}
	cin >> s >> t;
	--s, --t;
	memset(dist, -1, sizeof(dist));
	dist[s][0] = 0;
	queue<pii>que;
	que.push({ s,0 });
	while (!que.empty()) {
		pii cur = que.front();
		que.pop();
		int v = cur.first;
		int parity = cur.second;
		for (auto nv : G[v]) {
			int np = (parity + 1) % 3;
			if (dist[nv][np] == -1) {
				dist[nv][np] = dist[v][parity] + 1;
				que.push({ nv,np });
			}
		}
	}
	if (dist[t][0] == -1) {
		cout << -1 << endl;
	}
	else {
		cout << dist[t][0] / 3 << endl;
	}
	return 0;
}

joi　船旅
https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_f

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
struct edge { int to, cost; };
vector<edge>G[110];
int n, k;
int dis[110];
void dijkstra(int C,int D) {
	priority_queue<pii, vector<pii>,greater<pii>>que;
	for (int i = 0; i < 110; ++i) {
		dis[i] = INF;
	}
	dis[C] = 0;
	que.push({ 0,C });
	while (!que.empty()) {
		int c = que.top().first;
		int v = que.top().second;
		que.pop();
		if (dis[v] < c)continue;
		for (int i = 0; i < G[v].size(); ++i) {
			edge e = G[v][i];
			int cost = dis[v] + e.cost;
			if (dis[e.to] > cost) {
				dis[e.to] = cost;
				que.push({ cost,e.to });
			}
		}
	}
}
int main() {
    cin >> n >> k;
	for (int i = 0; i < k; ++i) {
		int a;
		cin >> a;
		if (a == 1) {
			int c, d, e;
			cin >> c >> d >> e;
			c--; d--;
			G[c].push_back({ d,e });
			G[d].push_back({ c,e });
		}
		else {
			int c, d;
			cin >> c >> d;
			c--; d--;
			dijkstra(c, d);
			if (dis[d]==INF) {
				cout << -1 << endl;
			}
			else {
				cout << dis[d] << endl;
			}
		}
	}
	return 0;
}

最小全域木
頂点の数10の場合
プリム法

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
int main() {
	int N, M;
	int cost[10][10];//cost[u][v]は辺e=(u,v)のコスト（存在しない場合はINF)
	int mincost[10];//集合Xからの辺の最小コスト
	bool used[10];//頂点iがXに含まれているかどうか
	cin >> N >> M;
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 10; ++j) {
			cost[i][j] = INF;
		}
	}
	for (int i = 0; i < M; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		cost[a][b] = c;
		cost[b][a] = c;
	}
	for (int i = 0; i < N; ++i) {
		mincost[i] = INF;
		used[i] = false;
	}
	mincost[0] = 0;
	int res = 0;
	while (true) {
		int v = -1;
		//Xに属さない頂点のうちXからの辺のコストが最小になる頂点を探す
		for (int u = 0; u < N; ++u) {
			if (!used[u] && (v == -1 || mincost[u] < mincost[v])) {
				v = u;
			}
		}
		if (v == -1)break;
		used[v] = true;
		res += mincost[v];
		for (int u = 0; u < N; ++u) {
			mincost[u] = min(mincost[u], cost[v][u]);
		}
	}
	cout << res << endl;
	return 0;
}

priority_queue プリム

struct edge { int to, cost; };
int v, e;
vector<edge>G[10010];
int mincost[10010];
bool used[10010];
int main() {
	cin >> v >> e;
	REP(i, v) {
		used[i] = false;
	}
	for (int i = 0; i < e; ++i) {
		int s, t, w;
		cin >> s >> t >> w;
		s--, t--;
		G[s].push_back({ t,w });
		G[t].push_back({ s,w });
	}
	priority_queue<pii, vector<pii>, greater<pii>>que;
	que.push({ 0,0 });
	ll res = 0;
	while (!que.empty()) {
		pii p = que.top();
		que.pop();
		int v = p.second;
		if (used[v])continue;
		res += p.first;
		used[v] = true;
		for (int i = 0; i < G[v].size(); ++i) {
			edge e = G[v][i];
			que.push({ e.cost,e.to });
		}
	}
	cout << res << endl;
	return 0;
}

クラスカル法

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
struct edge { int u, v, cost; };
edge es[5000];
int V, E;
vector<int>par;
vector<int>rnk;
void init_union_find(int n){
	par = vector<int>(n);
	rnk = vector<int>(n);
	for (int i = 0; i < n; ++i) {
			par[i] = i;
			rnk[i] = 0;
	}
}

int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
}

void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;//各木について木の高さ(rank)を記憶しておく
		if (rnk[x] < rnk[y]) {
			//併合の際に二つの木のrankが異なればrankの小さいものから大きいものへ辺を張る
			par[x] = y;
		}
		else {
			par[y] = x;
			if (rnk[x] == rnk[y])rnk[x]++;
		}
}
bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
}
//.......クラスカル法......//
bool comp(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}
int kruskal() {
	sort(es, es + E, comp);//edge.costの小さい順
	init_union_find(V);
	int res = 0;
	for (int i = 0; i < E; ++i) {
		edge e = es[i];
		if (!same(e.u, e.v)) {
			unite(e.u, e.v);
			res += e.cost;
		}
	}
	return res;
}
int main() {
	cin >> V >> E;
	for (int i = 0; i < E; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		edge e = { a,b,c };
		es[i] = e;
	}
	int res = kruskal();
	cout << res << endl;
	return 0;
}

built?

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
struct UnionFind {
	vector<int>par;

	UnionFind(int N) :par(N) {
		for (int i = 0; i < N; ++i) {
			par[i] = i;
		}
	}

	int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;
		par[rx] = ry;
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
//.......クラスカル法......//

int main() {
	int N;
	cin >> N;
	vector<pair<ll,int>>x, y;
	for (int i = 0; i < N; ++i) {
		ll a, b;
		cin >> a >> b;
		x.push_back({ a,i });
		y.push_back({ b,i });
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	using edge = pair<ll, pii>;
	vector<edge>edges;
	for (int i = 0; i < N-1; ++i) {
		int v1 = x[i].second;
		int v2 = x[i + 1].second;
		ll cost = x[i + 1].first - x[i].first;
		edges.push_back(edge(cost,pii(v1,v2)));
	}
	for (int i = 0; i < N-1; ++i) {
		int v1 = y[i].second;
		int v2 = y[i + 1].second;
		ll cost = y[i + 1].first - y[i].first;
		edges.push_back(edge(cost,pii(v1,v2)));
	}
	sort(edges.begin(), edges.end());
	UnionFind uf(N);
	ll ans = 0;
	for (auto e : edges) {
		int u = e.second.first, v = e.second.second;
		ll cost = e.first;
		if (!uf.same(u,v)) {
			uf.unite(u,v);
			ans += cost;
		}
	}
	cout << ans << endl;
	return 0;
}

indeedなう　game on a grid
最大全域木

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

struct UnionFind {
	vector<int>par;

	UnionFind(int N) :par(N) {
		for (int i = 0; i < N; ++i) {
			par[i] = i;
		}
	}

	int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;
		par[rx] = ry;
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};


int main() {
	int H, W;
	int Sx, Sy;
	int Gx, Gy;
	ll sum = 0;
	using edge = pair<int, pii>;
	vector<edge>G;
	int P[110][110];
	cin >> H >> W;
	cin >> Sx >> Sy;
	cin >> Gx >> Gy;
	Sx--, Sy--, Gx--, Gy--;
	pii st, go;
	for (int i = 0; i < H; ++i) {
		for (int j=0; j < W; ++j) {
			cin >> P[i][j];
			sum += P[i][j];
			if (i == Sy && j == Sx) {
				st = { i,j };
			}
			if (i == Gy && j == Gx) {
				go = { i,j };
			}
		}
	}
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			if (j + 1 < W) {
				G.push_back(edge(P[i][j] * P[i][j + 1], { i*W + j, i*W + j + 1 }));
			}
			if (i + 1 < H) {
				G.push_back(edge(P[i][j] * P[i + 1][j], { i*W + j,(i + 1)*W + j }));
			}
		}
	}
	sort(G.begin(), G.end(), greater<edge>());
	UnionFind uf(H*W);
	ll key = 0;
	for (auto e : G) {
		int u = e.second.first, v = e.second.second;
		ll cost = e.first;
		if (!uf.same(u, v)) {
			uf.unite(u, v);
			key += cost;
		}
	}
	cout << key + sum << endl;
	return 0;

}

abc 061 score attack
ベルマンフォードを少しひねったもの

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const ll INF = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int main() {
	int N, M;
	cin >> N >> M;
	const int NMAX = 1000;
	const int MMAX = 2000;
	int a[MMAX], b[MMAX];
	ll c[MMAX];
	for (int i = 0; i < M; ++i) {
		cin >> a[i] >> b[i] >> c[i];
		a[i]--, b[i]--;
		c[i] = -c[i];
	}
	ll dist[NMAX];
	for (int i = 0; i < N; ++i) {
		dist[i] = INF;
	}
	dist[0] = 0;
	for (int loop = 0; loop < N - 1; ++loop) {
		for (int i = 0; i < M; ++i) {
			if (dist[a[i]] == INF)continue;
			if (dist[b[i]] > dist[a[i]] + c[i]) {
				dist[b[i]] = dist[a[i]] + c[i];
			}
		}
	}
	ll ans = dist[N - 1];
	bool negative[NMAX];
	for (int i = 0; i < N; ++i) {
		negative[i] = false;
	}
	for (int loop = 0; loop < N; ++loop) {
		for (int i = 0; i < M; ++i) {
			if (dist[a[i]] == INF)continue;//関係にない負閉路は無視
			if (dist[b[i]] > dist[a[i]] + c[i]) {
				dist[b[i]] = dist[a[i]] + c[i];
				negative[b[i]] = true;
			}
			if (negative[a[i]] == true) {
				negative[b[i]] = true;
			}
		}
	}
	if (negative[N - 1]) {
		cout << "inf" << endl;
	}
	else {
		cout << -ans << endl;
	}
	return 0;
}

abc137 E

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const ll INF = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int main() {
	ll N, M, P;
	cin >> N >> M >> P;
	int a[5010], b[5010];
	ll c[5010];
	for (int i = 0; i < M; ++i) {
		cin >> a[i] >> b[i] >> c[i];
		a[i]--, b[i]--;
		c[i] = -(c[i] - P);
	}
	ll dist[2510];
	for (int i = 0; i < N; ++i) {
		dist[i] = INF;
	}
	dist[0] = 0;
	for (int loop = 0; loop < N - 1; ++loop) {
		for (int i = 0; i < M; ++i) {
			if (dist[a[i]] == INF)continue;
			if (dist[b[i]] > dist[a[i]] + c[i]) {
				dist[b[i]] = dist[a[i]] + c[i];
			}
		}
	}
	ll ans = dist[N - 1];
	bool negative[2510];
	for (int i = 0; i < N; ++i) {
		negative[i] = false;
	}
	for (int loop = 0; loop < N; ++loop) {
		for (int i = 0; i < M; ++i) {
			if (dist[a[i]] == INF)continue;//関係にない負閉路は無視
			if (dist[b[i]] > dist[a[i]] + c[i]) {
				dist[b[i]] = dist[a[i]] + c[i];
				negative[b[i]] = true;
			}
			if (negative[a[i]] == true) {
				negative[b[i]] = true;
			}
		}
	}
	if (negative[N - 1]) {
		cout << "-1" << endl;
	}
	else {
		if (ans > 0) {
			cout << 0 << endl;
		}
		else {
			cout << -ans << endl;
		}
	}
	return 0;
}

ワーシャルフロイド
abc 073 D

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int N, M, R;
int d[201][201];
int r[10];
int A, B, C;
int res;
bool used[10];
void dfs(int c, int las, int dist) {
	if (c == R) {
		if (res > dist)res = dist;
		return;
	}
	for (int i = 0; i < R; ++i) {
		if (!used[i]) {
			used[i] = true;
			if (las == -1) {
				dfs(c + 1, i, 0);
			}
			else {
				dfs(c + 1, i, dist + d[r[las]][r[i]]);
			}
			used[i] = false;
		}
	}
}
int main() {
	cin >> N >> M >> R;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (i != j)d[i][j] = INF;
			else d[i][j] = 0;
		}
	}
	for (int i = 0; i < R; ++i) {
		cin >> r[i];
		r[i]--;
	}
	for (int i = 0; i < M; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
	    d[a][b] = c;
		d[b][a] = c;
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			for (int k = 0; k < N; ++k) {
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}
	res = INF;
	dfs(0, -1, 0);
	cout << res << endl;
	return 0;

}

abc079 D wall

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
    if (x < y)swap(x, y);
    if (y == 0)return x;
    return gcd(y, x%y);
}
///////////////////////////////////////

//あらかじめ数xを数yに変換するための最小コストを計算しておく
int main() {
    int H, W;
    int C[10][10], A[202][202];
    cin >> H >> W;
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
            cin >> C[i][j];
        }
    }
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> A[i][j];
        }
    }
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
            for (int k = 0; k < 10; ++k) {
                C[j][k]= min(C[j][k], C[j][i] + C[i][k]);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (0 <= A[i][j]) {
                ans += C[A[i][j]][1];
            }
        }
    }
    cout << ans << endl;
    return 0;
}

abc 012 D

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int N, M;
int d[310][310];
int res;
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (i != j)d[i][j] = INF;
			else d[i][j] = 0;
		}
	}
	for (int i = 0; i < M; ++i) {
		int a, b, t;
		cin >> a >> b >> t;
		a--, b--;
		d[a][b] = t;
		d[b][a] = t;
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			for (int k = 0; k < N; ++k) {
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}
	res = INF;
	for (int i = 0; i < N; ++i) {
		int key = 0;
		for (int j = 0; j < N; ++j) {
			if (i == j)continue;
			key = max(key, d[i][j]);
		}
		res = min(res, key);
	}
	cout << res << endl;
	return 0;

}

線形計画法
Layout 牛ゲー
農夫はN頭の牛を飼っており各牛には１からNまでの番号がついている。これらは今番号順に一列に並んでいる。いくつかの牛は互いに仲が良くある距離以内に並びたいと考えておりまたいくつかの牛は非常に仲が悪くある距離以上離れて並びたいと考えている。また彼らはとても強引なので複数の牛がちょうど同じ場所に並ぶことも可能です。ML個の仲の良い牛の情報(AL,BL,DL)とMD個の仲の悪い牛の情報(AD,BD,DD)が与えられる。それぞれ牛ALとBLの間の最大距離DLならびに牛ADとBDの間の最小距離DDを表す。この制約を全てみたす並び方のうち1番の牛とN番の牛の間の最大距離を求めよ。もしそのような並び方が存在しない場合は-1を出力せよいくらでも離れることが可能な場合は-2を出力せよ。以下制約
2<=N<=1000
1<=ML,MD<=10000
1<=AL,BL<=N
1<=AD,BD<=N
1<=DL,DD<=1000000
解説
i番目の牛の位置をd[i]とする。まず番号順に並んでいるという条件からd[i]<=d[i+1]という不等式が成り立ちます。次に仲の良い牛の間の最大距離制約からd[AL]+DL>=d[BL]という不等式が成り立ちます。同様に各(AD,BD,DD)についてd[AD]+DD<=d[BD]という不等式が成り立ちます。したがってこれら3種類の不等式を同時に満たすようなdにおけるd[N]-d[1]の最大値を求める問題となる。これは線形計画問題であり、より簡単に解くことを考える。
この制約式の特徴はすべての式の両辺に変数が１つずつしか現れないことです。実はグラフの最短路問題もこのような形で表すこともできる。始点sから各頂点vへの最短距離をd(v)とする。するとコストwの辺e=(v,u)に対してd(v)+w>=d(u)という不等式がなりたつ。逆にこのような不等式をすべて満たすようなdにおけるd(v)-d(s)の最大値がsからvへの最短距離となっている。最小値ではなく最大値が最短距離に対応することに若干注意
もとの問題と最短路問題を見比べるとどちらも同じ形をしている。つまりもとの問題も各制約式が１つの辺に対応するようにグラフを作成することで最短路問題として解くことができる。まず頂点を1~Nとする。d[i]<=d[i+1]はd[i+1]+0>=d[i]と変形されるので頂点ALから頂点BLへコスト0の辺を張ることに対応する。同じようにd[AL]+DL>=d[BL]は頂点ALから頂点BLへコストDLの辺を張ることに対応しd[AD]+DD<=d[BD]は頂点BDから頂点ADへコスト-DDの辺を張ることに対応します。求めたいものはd[N]-d[1]の最大値でありこれは頂点１から頂点Nへの最短距離となります。グラフに負の辺が含まれるためベルマンフォード法を用いる。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
int N, ML, MD;
int AL[10010], BL[10010], DL[10010];
int AD[10010], BD[10010], DD[10010];

int d[1010];
int main() {
	cin >> N >> ML >> MD;
	for (int i = 0; i < ML; ++i) {
		cin >> AL[i] >> BL[i] >> DL[i];
	}
	for (int i = 0; i < MD; ++i) {
		cin >> AD[i] >> BD[i] >> DD[i];
	}
	fill(d, d + N, INF);
	d[0] = 0;
	//ベルマンフォード法によりdを計算する
	for (int k = 0; k < N; ++k) {
		//i+1からiへコスト0
		for (int i = 0; i + 1 < N; ++i) {
			if (d[i + 1] < INF) {
				d[i] = min(d[i], d[i + 1]);
			}
		}
		//ALからBLへコストDL
		for (int i = 0; i < ML; ++i) {
			if (d[AL[i] - 1] < INF) {
				d[BL[i] - 1] = min(d[BL[i] - 1], d[AL[i] - 1] + DL[i]);
			}
		}
		//BDからADへコスト-DD
		for (int i = 0; i < MD; ++i) {
			if (d[BD[i] - 1] < INF) {
				d[AD[i] - 1] = min(d[AD[i] - 1], d[BD[i] - 1] - DD[i]);
			}
		}
	}
	int res = d[N - 1];
	if (d[0] < 0) {
		//負の閉路が存在
		res = -1;

	}
	else if (res == INF) {
		res = -2;
	}
	cout << res << endl;
	return 0;

}

強連結成分分解

int V, E;
vector<int>G[10010];//グラフの隣接リスト表現
vector<int>rG[10010];//辺の向きを逆にしたグラフ
vector<int>vs;//帰りがけ順の並び
bool used[10010];//すでに調べたか
int cmp[10010];//属する強連結成分のトポロジカル順序
void add_edge(int from, int to) {
	G[from].push_back(to);
	rG[to].push_back(from);
}
void dfs(int v) {
	used[v] = true;
	for (int i = 0; i < G[v].size(); ++i) {
		if (!used[G[v][i]])dfs(G[v][i]);
	}
	vs.push_back(v);
}
void rdfs(int v, int k) {
	used[v] = true;
	cmp[v] = k;
	for (int i = 0; i < rG[v].size(); ++i) {
		if (!used[rG[v][i]])rdfs(rG[v][i], k);
	}
}
int main() {
	cin >> V >> E;
	REP(i, E) {
		int s, t;
		cin >> s >> t;
		G[s].push_back(t);
		rG[t].push_back(s);
	}
	int Q;
	cin >> Q;
	int num = 0;
	memset(used, 0, sizeof(used));
	vs.clear();
	for (int v = 0; v < V; ++v) {
		if (!used[v])dfs(v);
	}
	memset(used, 0, sizeof(used));
	for (int i = vs.size() - 1; i >= 0; i--) {
		if (!used[vs[i]])rdfs(vs[i], num++);
	}
	REP(i, Q) {
		int u, v;
		cin >> u >> v;
		if (cmp[u] == cmp[v]) {
			cout << 1 << endl;
		}
		else {
			cout << 0 << endl;
		}
	}
	return 0;
}