Advertisement
Guest User

Untitled

a guest
Apr 20th, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.32 KB | None | 0 0
  1. #include <iostream>
  2. #include<queue>
  3. #include<vector>
  4. #include<set>
  5. using namespace std;
  6. bool BFS(vector<bool>& used, vector<vector<int>>& G,
  7. queue<int>& nodes, int node, vector<int>& parents) {
  8. for (size_t i = 0; i < G[nodes.front()].size(); ++i) {
  9. if (node == G[nodes.front()][i]) {
  10. return true;
  11. }
  12. if (!used[G[nodes.front()][i]]) {
  13. used[G[nodes.front()][i]] = 1;
  14. nodes.push(G[nodes.front()][i]);
  15. parents[G[nodes.front()][i]] = nodes.front();
  16. }
  17. }
  18. nodes.pop();
  19. if (nodes.size() != 0) {
  20. return BFS(used, G, nodes, node, parents);
  21. }
  22. return false;
  23. }
  24. void Cin_vector(vector<vector<int> >& G, int quantity) {
  25. int first;
  26. for (int i = 1; i <= quantity; ++i) {
  27. for (size_t j = 1; j <= quantity; ++j) {
  28. cin >> first;
  29. if (first) {
  30. G[i].push_back(j);
  31. }
  32. }
  33. }
  34. }
  35. int main() {
  36. #pragma warning(disable:4996)
  37. freopen("input.txt", "r", stdin);
  38. freopen("output.txt", "w", stdout);
  39. vector<vector<int> > G;
  40. int quantity;
  41. cin >> quantity;
  42. G.resize(quantity + 1);
  43. Cin_vector(G, quantity);
  44. int node1, node2;
  45. cin >> node1 >> node2;
  46. vector<bool> used;
  47. used.resize(quantity + 1);
  48. used[1] = node2;
  49. queue<int> nodes;
  50. nodes.push(1);
  51. vector<int> parents;
  52. if (BFS(used, G, nodes, node1, parents)) {
  53. cout << "YES";
  54. }
  55. else {
  56. cout << "NO";
  57. }
  58. return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement