Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <sstream>
- #include <list>
- using namespace std;
- typedef vector<vector<int>> GraphType;
- list<size_t> get_neighbours(const GraphType& graph, const vector<bool>& visits, size_t target)
- {
- list<size_t> result;
- for (size_t i = 0; i < graph.size(); ++i)
- {
- if (0 != graph[target][i] && !visits[i])
- result.push_back(i);
- }
- return result;
- }
- void walk_some_vertice(const GraphType& graph, vector<bool>& visits, size_t target)
- {
- visits[target] = true;
- cout << "We are at node: " << target << endl;
- list<size_t> neighbours = get_neighbours(graph, visits, target);
- while(!neighbours.empty())
- {
- size_t new_target = neighbours.front();
- visits[new_target] = true;
- cout << "We are at node: " << new_target << endl;
- neighbours.splice(end(neighbours), get_neighbours(graph, visits, new_target));
- neighbours.pop_front();
- }
- }
- void breadth_walk(const GraphType& graph)
- {
- vector<bool> visited(graph.size(), false);
- for(size_t i = 0; i < graph.size(); ++i)
- {
- if (!visited[i])
- walk_some_vertice(graph, visited, i);
- }
- }
- int main()
- {
- GraphType graph;
- unsigned N;
- cin >> N;
- graph.resize(N, vector<int>(N, 0));
- string line;
- getline(cin, line);
- for (unsigned i = 0; i < N; ++i)
- {
- getline(cin, line);
- stringstream x(line);
- size_t neighbour;
- while (x >> neighbour)
- {
- graph[i][neighbour] = 1;
- graph[neighbour][i] = 1;
- }
- graph[i][i] = 0;
- }
- for(auto line : graph)
- {
- for(int val: line)
- cout << val << '\t';
- cout << endl;
- }
- breadth_walk(graph);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement