閉路　dfs とか

dfsによる閉路検出

```
#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;
}
///////////////////////////////////////

bool v[110][110], used[110], used2[110];
int V, E;
bool dfs(int p) {
	if (used[p])return 1;
	if (used2[p])return 0;
	used2[p] = 1;
	for (int i = 0; i<V; ++i) {
		if (v[p][i]) {
			used[p] = 1;
			if (dfs(i))return 1;
			used[p] = 0;
		}
	}
	return 0;
}
int main() {
	cin >> V >> E;
	for (int i = 0; i < E; ++i) {
		int s, t; cin >> s >> t;
		v[s][t] = 1;
	}
	for (int i = 0; i < V; ++i) {
		if (!used2[i] && dfs(i)) {
			cout << 1 << endl;
			return 0;
		}
	}
	cout << 0 << 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;
}
///////////////////////////////////////

int V, E;
vector<int>G[110];
bool used1[110];//探索中に同じところを通ったら閉路があるとみなすフラグ
bool used2[110];//一回探索したことがあるか?のフラグ
bool dfs(int u) {
	if (used1[u])return true;
	used1[u] = true;
	for (int i = 0; i < G[u].size(); ++i) {
		if (used2[G[u][i]])continue;
		if (dfs(G[u][i]))return true;
	}
	used2[u] = true;
	used1[u] = false;
	return false;
}
int main() {
	cin >> V >> E;
	for (int i = 0; i < E; ++i) {
		int s, t; cin >> s >> t;
		G[s].push_back(t);
	}
	fill(used2, used2 + 110, false);
	for (int i = 0; i < 110; ++i) {
		fill(used1, used1 + 110, false);
		if (used2[i])continue;
		if (dfs(i)) {
			cout << 1 << endl;
			return 0;
		}
	}
	cout << 0 << endl;
	return 0;
}
```
行きがけと帰りがけ

```
//行きがけ帰りがけ
vector<bool>seen;
vector<int>first_order;//いきがけ順
vector<int>last_order;//帰りがけ順
int first_ptr = 0;
int last_ptr = 0;
void dfs( Graph G, int v) {
	first_order[v] = first_ptr++;
	seen[v] = true;
	for (auto next_v : G[v]) {
		if (seen[next_v])continue;
		dfs(G, next_v);
	}
	last_order[v] = last_ptr++;
}
int main() {
	int n, m; cin >> n >> m;
	Graph G(n);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	seen.assign(n, false);
	first_order.resize(n);
	last_order.resize(n);
	dfs(G, 0);
	for (int v = 0; v < n; ++v) {
		cout << v << ": " << first_order[v] << "," << last_order[v] << endl;
	}
	return 0;
}
```
タイムスタンプ
最初に発見した段階と、vv の子孫たちも含めて探索を終えた段階とを表すもので、(前者)/(後者) として表したりする

```
void dfs(const Graph &G, int v, int& ptr) {
    // 行きがけ順をインクリメントしながらメモ
    first_order[v] = ptr++;

    seen[v] = true; 
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue;
        dfs(G, next_v, ptr);
    }

    // 帰りがけ順をインクリメントしながらメモ
    last_order[v] = ptr++;
}
```
二部グラフ判定　even relationなど

```
int N;
vector<pii>g[100100];
int ans[100100];
bool seen[100100];
void dfs(int v,int p) {
	if (seen[v])return;
	ans[v] = p;
	seen[v] = true;
	for (auto x : g[]) {
		if (x.second % 2 == 0) {
			dfs(x.first, p);
		}
		else {
			dfs(x.first, 1 - p);
		}
	}
}
int main() {
	cin >> N;
	REP(i, N-1) {
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		g[u].push_back({ v,w });
		g[v].push_back({ u,w });
		seen[i] = false;
	}
	dfs(0,0);
	REP(i, N) {
		cout << ans[i] << endl;
	}
	return 0;
}
```
例題
りんごさんは 
N頂点 の連結な無向グラフを持っています。 このグラフにはすでに M本の辺があり、
i本目の辺は頂点 Aiと頂点 Biを繋いでいます。
りんごさんは以下の操作を行うことで、辺を追加しようと思っています。
操作：頂点 uから辺をちょうど 3本辿ることによって頂点 vに辿り着けるような u,v(u≠v)をとり、頂点 uと頂点 vの間に辺を追加する。ただし、すでに頂点 uと頂点 vの間に辺が存在する場合は辺を追加することはできない。りんごさんが追加できる辺の本数の最大値を求めて下さい。 codefestival2017 c