Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const int MAX_SIZE = 100;
- bool used[MAX_SIZE] = {false,};
- bool hasPath(vector<vector<int>> graph, int a, int b){
- if(a == b){
- // cout<<a<<"=="<<b<<endl;
- return true;
- }
- else{
- used[a] = true;
- cout<<"used["<<a<<"]="<<1<<endl;
- cout<<"size: "<<graph[a].size()<<endl;
- for(unsigned i = 0; i<graph[a].size(); i++){
- if(used[graph[a][i]] == 0){
- //cout<<graph[a][i]<<" ->"<<b<<endl;
- // used[graph[a][i]] = true;
- used[graph[a][i]] = true;
- return hasPath(graph, graph[a][i], b);
- used[graph[a][i]] = true;
- }
- }
- // used[a] = true;
- }
- return false;
- }
- int main()
- {
- int n = 10;
- vector<vector<int>> graph(n);
- int m = 5;
- for(int i = 0; i<m; i++){
- int first, second;
- cin>>first>>second;
- graph[first].push_back(second);
- graph[second].push_back(first);
- }
- for(int i =0; i<10; i++){
- cout<<i<<" : ";
- for(int j = 0; j<graph[i].size(); j++){
- cout<<graph[i][j]<<" ";
- }
- cout<<endl;
- }
- int a = 1, b = 5;
- cout<<"Has path between 1 and 5 : "<<hasPath(graph,a,b)<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement