摘要：
路径[i]；=nvset[i]=真；vset[i]=假；intn；i++）put（路径[i]）；看跌期权（“”）；col[i]&；n和=0&；nj<；j++）｛scanf（“%d”；｝｝vset[0][0]=0；&；前提条件）｛vector<；n<；n；y=前提条件[i][1]；
图的遍历和应用
- 实现方式：邻接矩阵可以使用vector。邻接矩阵的无穷表示方法：
memset( road, 0x3f, sizeof(road) ); - 应用场景：拓扑图、最小生成树、最短路径、二分图、DFS、BFS。
全排列问题
const int N = 7;
int path[N+1]; bool vset[N+1];
int n;
void dfs(int x) {
if(x == n) {
for(int i = 0; i < n; i++) cout << path[i];
cout << endl;
}
else {
for(int i = 1; i <= n; i++ ) {
if (vset[i] == false) {
path[x] = i;
vset[i] = true;
dfs(x+1);
vset[i] = false; //恢复现场
}
}
}
}
int main() {
scanf("%d", &n);
memset(vset, false, sizeof vset);
dfs(0);
}
n皇后
const int N = 10;
char path[N+1][N+1];
bool col[N], zp[2*N], xp[2*N];
int n;
void dfs(int x) {
if(x == n) {
for(int i = 0; i < n; i++) puts(path[i]);
puts("");
}
else {
for(int i = 0; i < n; i++) {
if (!col[i] && !zp[x + i] && !xp[n - x + i ]) {
path[x][i] = 'Q';
col[i] = zp[x + i] = xp[n - x + i ] = true;
dfs(x+1);
path[x][i] = '.';
col[i] = zp[x + i] = xp[n - x + i ] = false;
}
}
}
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
for (int j = 0; j < n; j++){
path[i][j] = '.';
}
}
dfs(0); //每层遍历
}
迷宫问题
const int N = 100, M = 100;
int path[N][M], vset[N][M];
int n, m;
typedef pair<int, int> PII;
PII q[N * N];
void bfs() {
int front = 0, rear = 0; //指向的就是队头和队尾 没有多开其他空间
q[0] = {0, 0};
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while(front<=rear) {
auto t = q[front++];
for(int i = 0; i < 4; i++) {
int x = t.first + dx[i], y = t.second + dy[i];
if(x>=0 && x<n && y>=0 && y< m && vset[x][y] == -1 && path[x][y] == 0) {
vset[x][y] = vset[t.first][t.second] + 1;
q[++rear] = {x, y};
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) {
for (int j = 0; j < m; j++){
scanf("%d", &path[i][j]);
vset[i][j] = -1;
}
}
vset[0][0] = 0;
bfs();
printf("%d", vset[n-1][m-1]);
}
有向图的拓扑排序 O(n+e)
/**
1. 采用邻接表思想，将vector初始化，每读入一条边，则向v中加入相关结点。
2. indegree存入度数，结点入队列存储。如果最后入队元素个数等于结点总个数，则返回读入顺序数组，否则返回空数组。
**/
int x, y, n;
queue<int> q;
vector<int> v;
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> G[numCourses];
n = prerequisites.size();
cout << n << " ";
int indegree[numCourses];
for(int i = 0; i < numCourses; i++) {
indegree[i] = 0;
}
for(int i = 0; i < n; i ++) {
x = prerequisites[i][0];
y = prerequisites[i][1];
indegree[x]++;
G[y].push_back(x);
}
for(int i = 0; i < numCourses; i++) {
cout << indegree[i] << " ";
}
for(int i = 0; i < numCourses; i++) {
if(indegree[i]==0)
{
q.push(i);
}
}
while(!q.empty()) { // 判断队列是否为空
int p = q.front();
q.pop();
v.push_back(p);
for(int j = 0; j < G[p].size(); j++) {
int k = G[p][j];
--indegree[k];
if(indegree[k]==0) q.push(k);
}
}
if(v.size() == numCourses) return v;
else {
v.clear();
return v;
}
}
染色法判断二分图
bool check(AGragh *g) {
int n = g.n;
// 初始化color数组
// memset(color, -1, sizeof color);
int color[maxsize];
for(int i = 0; i < g.n; i++ ) {
color[i] = -1;
}
int flag = true;
for(int i = 0; i < n; i++) {
if(color[i] == -1) { // 遍历数组 找到一个未被染色结点
if(!dfs(i, 0)) { // 对该结点进行深度优先染色 失败时修改flag
flag = false; break;
}
}
}
return flag;
}
bool dfs(int x, int c) { // x是结点 c为结点需要染的颜色
color[x] = c;
// 首先将结点x染色 然后遍历其邻接点 染成相反的颜色
AcrNode *p = g->adjList[x].firstarc;
while(p){
int k = p->adjvex;
if(!color[k]) { //假如其邻接点未被染的 继续深度遍历染色 颜色取反 真是妙啊
if(!dfs(k,!c)) return false;
p = p->nextarc;
} else if(color[k] == c) return false; // 如果该点已经被染色 而且颜色相同的话 返回false
}
return ture;
}
匈牙利算法 —— 最大匹配
int match[n]; //match存储的是 右侧点匹配的点
bool st[n]; // 该点是否已经被访问过
int main(AGragh *g) {
int n = g.n;
int res = 0;
memset(st, false, sizeof st);
memset(match, 0, sizeof match);
for(int i = 0; i < n; i++) {
if(find(i)) res++; //对每个点进行匹配
}
}
bool find(int x) {
ArcNode *p = g->adjList[x].firstArc;
while(p) {
int j = p->adjvex;
if(!st[j]){
st[j] = true; // 如果j结点没有被匹配 或者说 匹配的那个对象可以找到其他人
if(match[j] == 0 || find(match[j])) {
match[j] = x;
return true;
}
p = p->nextarc; // 如果已经被匹配就找下一个结点
}
}
return false; //结束了循环还没有被返回 则表明没有找到可以匹配的结点
}
代码与知识点均学习自AcWing：https://www.acwing.com/activity/