Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include<queue>
- #include<vector>
- #include<set>
- using namespace std;
- bool BFS(vector<bool>& used, vector<vector<int>>& G,
- queue<int>& nodes, int node, vector<int>& parents) {
- for (size_t i = 0; i < G[nodes.front()].size(); ++i) {
- if (node == G[nodes.front()][i]) {
- return true;
- }
- if (!used[G[nodes.front()][i]]) {
- used[G[nodes.front()][i]] = 1;
- nodes.push(G[nodes.front()][i]);
- parents[G[nodes.front()][i]] = nodes.front();
- }
- }
- nodes.pop();
- if (nodes.size() != 0) {
- return BFS(used, G, nodes, node, parents);
- }
- return false;
- }
- void Cin_vector(vector<vector<int> >& G, int quantity) {
- int first;
- for (int i = 1; i <= quantity; ++i) {
- for (size_t j = 1; j <= quantity; ++j) {
- cin >> first;
- if (first) {
- G[i].push_back(j);
- }
- }
- }
- }
- int main() {
- #pragma warning(disable:4996)
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- vector<vector<int> > G;
- int quantity;
- cin >> quantity;
- G.resize(quantity + 1);
- Cin_vector(G, quantity);
- int node1, node2;
- cin >> node1 >> node2;
- vector<bool> used;
- used.resize(quantity + 1);
- used[1] = node2;
- queue<int> nodes;
- nodes.push(1);
- vector<int> parents;
- if (BFS(used, G, nodes, node1, parents)) {
- cout << "YES";
- }
- else {
- cout << "NO";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement