bfs/dfs_problem_list

//https://vjudge.net/problem/uva-762////find path destination
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
map<string, vector<string>> adj;
map<string, int> level;
map<string, string> root;
void bfs(string source) {
  level.clear();
  level[source] = 1;
  queue<string> que;
  que.push(source);
  while (!que.empty()) {
    string peek = que.front();
    que.pop();
    for (auto u : adj[peek]) {
      if (level[u] == 0) {
        que.push(u);
        level[u] = level[peek] + 1;
        root[u] = peek;
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  bool ok=false;
  while (cin >> n) {
    if ( ok ) cout << endl;
    ok = true;
    adj.clear();
    root.clear();
    for (int i = 0; i < n; i++) {
      string s1, s2;
      cin >> s1 >> s2;
      adj[s1].push_back(s2);
      adj[s2].push_back(s1);
    }
    string source, des;
    cin >> source >> des;
    bfs(source);
    if (level[des] == 0) {
      cout << "No route"
           << "\n";
      continue;
    }
    vector<pair<string, string>> res;
    while (!root[des].empty()) {
      res.push_back({root[des], des});
      des = root[des];
    }
    reverse(res.begin(), res.end());
    for (auto v : res) {
      cout << v.first << " " << v.second << "\n";
    }
  }
  return 0;
}



problem link:https://vjudge.net/problem/UVA-10004////Bicolor or not
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int mx = 205;
vector<int> adj[mx];
int color[mx];
bool isBi(int source) {
  memset(color, -1, sizeof(color));
  color[mx] = 1;
  queue<int> que;
  que.push(source);
  while (!que.empty()) {
    int peek = que.front();
    que.pop();
    for (auto u : adj[peek]) {
      if (color[u] == -1) {
        que.push(u);
        if (color[peek] == 1) {
          color[u] = 2;
        } else {
          color[u] = 1;
        }
      } else if (color[peek] == color[u]) {
        return false;
      }
    }
  }
  return true;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  while (true) {
    int n, e;
    cin >> n;
    if (n == 0) {
      break;
    }
    cin >> e;
    for (int i = 0; i < e; i++) {
      int u, v;
      cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
    if (isBi(0)) {
      cout << "BICOLORABLE.\n";
    } else {
      cout << "NOT BICOLORABLE.\n";
    }
    for (int i = 0; i <= mx; i++) {
      adj[i].clear();
    }
  }
  return 0;
}



problem link:https://lightoj.com/problem/jane-and-the-frost-giants/////print the case number and IMPOSSIBLE if Jane cannot escape from the maze before fire reaches her, or the earliest time for Jane to safely escape from the maze, in minutes.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int mx = 205;
char grid[mx][mx];
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
vector<pair<int, int>> fire;
int fire_level[mx][mx];
int man_level[mx][mx];
int n, m;
void bfs_fire() {
  memset(fire_level, -1, sizeof(fire_level));
  queue<pair<int, int>> que;
  for (int i = 0; i < fire.size(); i++) {
    que.push({fire[i].first, fire[i].second});
    fire_level[fire[i].first][fire[i].second] = 0;
  }
  while (!que.empty()) {
    int x = que.front().first;
    int y = que.front().second;
    que.pop();
    for (int i = 0; i < 4; i++) {
      int x1 = x + dx[i];
      int y1 = y + dy[i];
      if (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m &&
          fire_level[x1][y1] == -1 && grid[x1][y1] != '#') {
        fire_level[x1][y1] = fire_level[x][y] + 1;
        que.push({x1, y1});
      }
    }
  }
}
void bfs_man(int s1, int s2) {
  memset(man_level, -1, sizeof(man_level));
  queue<pair<int, int>> que;
  man_level[s1][s2] = 0;
  que.push({s1, s2});
  while (!que.empty()) {
    int x = que.front().first;
    int y = que.front().second;
    que.pop();
    for (int i = 0; i < 4; i++) {
      int x1 = x + dx[i];
      int y1 = y + dy[i];
      if (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m && man_level[x1][y1] == -1 &&
          man_level[x][y] + 1 < fire_level[x1][y1] && grid[x1][y1] != '#') {
        man_level[x1][y1] = man_level[x][y] + 1;
        que.push({x1, y1});
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt, k = 1;
  cin >> tt;
  while (tt--) {
    fire.clear();
    cin >> n >> m;
    int x = 0, y = 0;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        cin >> grid[i][j];
        if (grid[i][j] == 'J') {
          x = i, y = j;
        } else if (grid[i][j] == 'F') {
          fire.push_back({i, j});
        }
      }
    }
    bfs_fire();
    bfs_man(x, y);
    int low = INT_MAX;
    for (int i = 1; i <= n; i++) {
      if (man_level[i][1] != -1) {
        low = min(low, man_level[i][1]);
      }
    }
    for (int i = 1; i <= n; i++) {
      if (man_level[i][m] != -1) {
        low = min(low, man_level[i][m]);
      }
    }
    for (int i = 1; i <= m; i++) {
      if (man_level[1][i] != -1) {
        low = min(low, man_level[1][i]);
      }
    }
    for (int i = 1; i <= m; i++) {
      if (man_level[n][i] != -1) {
        low = min(low, man_level[n][i]);
      }
    }
    cout << "Case " << k++ << ": ";
    if (low == INT_MAX) {
      cout << "IMPOSSIBLE\n";
    } else {
      cout << low + 1 << "\n";
    }
  }
  return 0;
}