算法-DFS+BFS+拓扑排列

DFS例题acwing842vectorintnum;vectorboolused;int n;void dfs(vectorint 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;}vectorintselected {};dfs(selected);return 0;}BFS例题acwing844int n, m;vectorvectorintgraph;vectorvectorintans; //不用used数组直接存储所有的答案int dirx[4] { -1,1,0,0 };int diry[4] { 0,0,-1,1 };void bfs(){queuepairint, intque;que.push({ 0,0 });ans[0][0] 0; //要单独初始化为0while (!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, vectorint(m));ans.resize(n, vectorint(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;}拓扑排序例题acwing848int n, m;vectorvectorintgraph;vectorintans;vectorintindegree;void bfs(){queueintque;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;elsefor (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;}