DFS

DFS

深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树和图的算法。它沿着树或图的每一分支尽可能深入，直到到达叶节点或无法前进时再回溯。

排列

#include <bits/stdc++.h>
#define int long long
using namespace std;
// 全排列问题
// 一个个填数字，每次填的数字和前面的不一样	

const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u) {
	if (u == n) {
		for (int i = 0; i < n; i++) cout << path[i];
		cout << endl;
		return;
	}
	for (int i = 1; i <= n; i++) {
		// 如果这个数没有被选过
		if (!st[i]) {
			path[u] = i;
			st[i] = true;
			dfs(u + 1);
			// 回溯的时候注意恢复现场
			st[i] = false;
		}
	}
}

void solve() {
	cin >> n;
	dfs(0);
	
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

字符串的全排序

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100;
int n;
string str;
char path[N];
bool st[N];

void dfs(int u) {
	for (int i = 0; i <= u; i++) cout << path[i];
	cout << endl;
	for (int i = 0; i < n; i++) {
		if (!st[i]) {
			path[u] = str[i];
			st[i] = true;
			dfs(u + 1);
			path[u] = '\0';
			st[i] = false;
		}
	}
}

void solve() {
	cin >> n;
	cin >> str;
	dfs(0);
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

n皇后问题(按行枚举)

#include <bits/stdc++.h>
#define int long long
using namespace std;

// 枚举皇后在每行中的位置
// 实际上也相当于是一个排列问题

// col[i]实现了
/*
	   0 1 2 3 4
	
	0  0 1 2 3 4
	1  0 1 2 3 4
	2  0 1 2 3 4
	3  0 1 2 3 4
	4  0 1 2 3 4
*/

// dg[u + i]实现了
/*
	   0 1 2 3 4
	
	0  0 1 2 3 4
	1  1 2 3 4 5
	2  2 3 4 5 6
	3  3 4 5 6 7
	4  4 5 6 7 8
*/

// dg[n - (u - i)]实现了
/*
	   0 1 2 3 4
	
	0  4 5 6 7 8
	1  3 4 5 6 7
	2  2 3 4 5 6
	3  1 2 3 4 5
	4  0 1 2 3 4			
*/
const int N = 20;
char g[N][N];
bool col[N], dg[N], udg[N];
int n;

void dfs(int u) {
	if (u == n) {	
		for (int i = 0; i < n; i++) puts(g[i]);
		puts("");
		return;
	}
	for (int i = 0; i < n; i++) {
		// 判断 u 行 i 列是否可以放皇后
		if (!col[i] && !dg[u + i] && !udg[n - (u - i)]) {
			g[u][i] = 'Q';
			col[i] = dg[u + i] = udg[n - (u - i)] = true;
			dfs(u + 1);
			col[i] = dg[u + i] = udg[n - (u - i)] = false;
			g[u][i] = '.';
		}
	}
}

void solve() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			g[i][j] = '.';
		}
	}
	dfs(0);
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

n皇后(一个个枚举)

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n;
const int N = 20;

char g[N][N];
bool row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s) {
	if (y == n) {
		y = 0;
		x++;
	}
	if (x == n) {
		if (s == n) {
			for (int i = 0; i < n; i++) puts(g[i]);
			puts("");
		}
		return;
	}
	/*
			 o
	       y/ \n
		  o     o
	    y/ \n y/ \n
	    o   o o   o
		
	*/
	
	// 不放皇后
	dfs(x, y + 1, s);
	
	// 放皇后
	if (!row[x] && !col[y] && !dg[x + y] && !udg[n - (x - y)]) {
		g[x][y] = 'Q';
		row[x] = col[y] = dg[x + y] = udg[n - (x - y)] = true;
		dfs(x, y + 1, s + 1);
		row[x] = col[y] = dg[x + y] = udg[n - (x - y)] = false;
		g[x][y] = '.';
	} 

}

void solve() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			g[i][j] = '.';
		}
	}
	dfs(0, 0, 0);
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

双向广搜

https://www.luogu.com.cn/problem/P4799

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m;

void dfs(int l, int r, int temp, vector<int>& sum, vector<int>& arr) {
	// 剪枝
	if (temp > m) return;
	if (l == r) {
		sum.push_back(temp);
		return;
	}
	// 不选
	dfs(l + 1, r, temp, sum, arr);
	// 选
	dfs(l + 1, r, temp + arr[l], sum, arr);
}


void solve() {
	cin >> n >> m;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) cin >> arr[i];
	vector<int> left, right;
	dfs(0, n / 2, 0, left, arr);
	dfs(n / 2, n, 0, right, arr);
	sort(left.begin(), left.end());
	sort(right.begin(), right.end());
	int l_len = left.size();
	int r_len = right.size();
	int ans = 0;
	for (int i = 0, j = r_len - 1; i < l_len; i++) {
		while (j >= 0 && left[i] + right[j] > m) {
			j--;
		}
		if (j >= 0) ans += (j + 1);
	}
	cout << ans << endl;
}
signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

树的重心

#include <bits/stdc++.h>/
#define int long long
//#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
const int mod = 1e9 + 7;

int n;
vector<vector<int>> g;
vector<bool> vis;

int ans = INT_MAX;

// 寻找树的重心

// 依次删除每个点，求出连通块的最大值
// 再求出所有最大值的最小值
// 删除一个点后，整体可以可以分为两部分
// 一部分是这个点的子节点，以这个子节点为根的子树的大小
// 另一部分是剩余的大小 n - sum

// 返回以 u 为根的子树的大小
int dfs(int u) {
	vis[u] = true;
	// sum：以 u 为根的子树的大小 
	// res：连通块的最大值
	int sum = 1, res = INT_MIN;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (!vis[v]) {
			// s： 以 v 为根的子树的大小
			int s = dfs(v);
			res = max(res, s);
			sum += s;
		}
	}
	res = max(res, n - sum);
	ans = min(ans, res);
	return sum;
}

void solve() {
	cin >> n;
	g.resize(n + 1);
	vis.assign(n + 1, false);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}