算法-DFS+BFS+拓扑排列

DFS

例题：acwing842

vector<int>num;
vector<bool>used;
int n;
void dfs(vector<int>& selected)
{
if (selected.size() == n)
{
for (int i = 0; i < n; i++)
{
cout << selected[i] << ' ';
}
cout << endl;
return;
}
for (int i = 0; i < n; i++)
{
if (!used[i])
{
used[i] = true;
selected.push_back(num[i]);
dfs(selected);
used[i] = false; //一定used和selected都要还原
selected.pop_back();
}
}
}

int main()
{
cin >> n;
num.resize(n);
used.resize(n);
for (int i = 0; i < n; i++)
{
num[i] = i + 1;
}
vector<int>selected = {};
dfs(selected);
return 0;
}

BFS

例题：acwing844

int n, m;
vector<vector<int>>graph;
vector<vector<int>>ans; //不用used数组，直接存储所有的答案
int dirx[4] = { -1,1,0,0 };
int diry[4] = { 0,0,-1,1 };
void bfs()
{
queue<pair<int, int>>que;
que.push({ 0,0 });
ans[0][0] = 0; //要单独初始化为0
while (!que.empty())
{
auto curr = que.front();
que.pop();
for (int i = 0; i < 4; i++)
{
int currx = curr.first + dirx[i];
int curry = curr.second + diry[i];
if (!(currx >= 0 && currx < n && curry >= 0 && curry < m))
continue;
if (ans[currx][curry] != -1 || graph[currx][curry] == 1) //一定要判断是不是障碍物
continue;
que.push(make_pair(currx, curry));
ans[currx][curry] = ans[curr.first][curr.second] + 1;
}
}
}

int main()
{
cin >> n >> m;
graph.resize(n, vector<int>(m));
ans.resize(n, vector<int>(m, -1));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
cin >> graph[i][j];
}
bfs();
cout << ans[n - 1][m - 1] << endl;
return 0;
}

拓扑排序

例题：acwing848

int n, m;
vector<vector<int>>graph;
vector<int>ans;
vector<int>indegree;
void bfs()
{
queue<int>que;
for (int i = 1; i <= n; i++)
{
if (!indegree[i])
que.push(i);
}
while (!que.empty())
{
auto curr = que.front();
ans.push_back(curr);
que.pop();
for (int i = 0; i < graph[curr].size(); i++)
{
int temp = graph[curr][i];
indegree[temp]--;
if (!indegree[temp])
que.push(temp);
}
}
if (ans.size() != n)
cout << -1 << endl;
else
for (int i = 0; i < n; i++)
{
cout << ans[i] << ' ';
}
}

int main()
{
cin >> n >> m;
graph.resize(n + 1);
indegree.resize(n + 1, 0);
while (m--)
{
int a, b;
cin >> a >> b;
graph[a].push_back(b);
indegree[b]++; //记得统计入度
}
bfs();
return 0;
}