文章目录
DFS
排列数字
#include<iostream>
using namespace std;
int n ;
int a[10];
bool s[10];
void dfs(int u)
{
if(u == n)
{
for(int i = 0 ; i <n ; i++) cout << a[i] << " " ;
cout << endl ;
return;
}
for(int i = 1; i <= n ; i++)
{
if(!s[i])
{
a[u] = i;
s[i] = true ;
dfs(u+1);
a[u] = 0 ;
s[i] = false;
}
}
}
int main()
{
cin >> n ;
dfs(0);
return 0;
}
n皇后
#include<iostream>
using namespace std;
const int N = 20 ;
char g[N][N] ;
bool c[N], x[N] , y[N];
int n , m ;
void dfs(int u)
{
if(u == n)
{
for(int i = 0 ; i < n; i++) cout << g[i] << endl;
cout << endl;
return ;
}
for(int i = 0 ; i < n ; i++)
{
if(!c[i] && !x[u+i] && !y[u-i+n])
{
c[i] = x[u+i] = y[u-i+n] = true ;
g[u][i] = 'Q';
dfs(u+1);
g[u][i] = '.';
c[i] = x[u+i] = y[u-i+n] = false ;
}
}
}
int main()
{
cin >> n;
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
g[i][j] = '.' ;
dfs(0);
return 0 ;
}
BFS
走迷宫
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> PII ;
const int N = 110 ;
PII q[N * N];
int f[N][N] , d[N][N];
int n , m ;
int dx[] = {0,1,0,-1} , dy[] = {1,0,-1,0} ;
int bfs()
{
memset(d , -1 , sizeof d);
d[1][1] = 0 ;
q[0] = {1,1};
int hh = 0 , tt = 0 ;
while(hh <= tt)
{
auto t = q[hh++] ;
for(int i = 0 ; i < 4 ; i++)
{
int x = t.first + dx[i] , y = t.second + dy[i] ;
if(x<=n &&x>0 && y<=m && y>0 && d[x][y] == -1 && f[x][y] == 0)
{
q[++tt] = {x,y};
d[x][y] = d[t.first][t.second] + 1 ;
}
}
}
return d[n][m];
}
int main()
{
cin >> n >> m ;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= m ; j++)
cin >> f[i][j];
cout << bfs();
return 0;
}
拓扑序列
单链表
点击跳转至例题
idx存的是指针
树与图的深度优先搜索
树的重心
每个节点都是一个单链表
模拟队列
hh = 0 , tt = -1
有向图的拓扑序列
都是从前指向后,即有向无环图（不能有环）
所有入度为0的点，都能排在前面的位置
删掉t->j的边，仅仅是j的入度减一，当j的入度为0的时候，放入队列
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int n , m ;
int e[N] , h[N] , ne[N] , idx;
int d[N] , q[N];
void add(int a , int b)
{
e[idx] = b , ne[idx] = h[a] , h[a] = idx++;
}
bool topool()
{
int hh = 0 , tt = -1 ;
for(int i = 1; i <= n ; i++)
if(!d[i]) q[++tt] = i ;
while(hh <= tt)
{
int t = q[hh++];
for(int i = h[t] ; i != -1 ; i = ne[i])
{
int j = e[i];
d[j] -- ;
if(d[j] == 0) q[++tt] = j ;
}
}
return tt == n - 1;
}
int main()
{
cin >> n >> m ;
memset(h , -1 , sizeof h) ;
for(int i = 0 ; i < m ; i++)
{
int x,y;
cin >> x >> y;
add(x,y);
d[y]++;
}
if(topool())
{
for(int i = 0 ; i < n ; i++) cout << q[i] << " " ;
}
else cout << -1 ;
return 0;
}
