1 files changed, 62 insertions, 0 deletions
diff --git a/10009/roads.cpp b/10009/roads.cpp
new file mode 100644
index 0000000..f14b731
--- /dev/null
+++ b/10009/roads.cpp
@@ -0,0 +1,62 @@
+#include <iostream>
+#include <vector>
+#include <string>
+#include <queue>
+#include <stack>
+using namespace std;
+
+int main(){
+    int tc;
+    cin>>tc;
+    while(tc--){
+	int r, q, c1, c2;
+	char city1[100], city2[100];
+
+	int map[26][26] = {0};		
+	cin>>r>>q;
+	while(r--){
+	    cin>>city1>>city2;
+	    c1 = (int)city1[0] % 65;
+	    c2 = (int)city2[0] % 65;
+
+	    map[c1][c2] = 1;
+	    map[c2][c1] = 1;
+	}       
+	
+	while(q--){
+	    string path="";
+	    cin>>city1>>city2;
+	    c1 = (int)city1[0] % 65;
+	    c2 = (int)city2[0] % 65;
+
+	    //BFS 
+	    bool visited[26]={false};
+	    stack<int> s;
+	    stack<string> p;
+	    int start = c1;
+	    string c;	    
+	    s.push(start);
+	    
+	    c = char(s.top()+65);
+	    p.push(c);
+	    p.push(c);
+	    while(s.top()!=c2){		
+		start = s.top();
+		s.pop();
+		visited[start]=true;	       
+		for(int i=0; i<26; i++)
+		    if(start!=i && map[start][i]==1 && !visited[i])
+			    s.push(i);
+	    }
+	    
+	    // for(int i=0; i<s.size(); i++){
+	    // 	c= char(s.top()+65);
+	    // 	path+=c;
+	    // 	s.pop();
+	    // }
+	    
+	    cout<<path<<endl;
+	} 	
+    }
+}
+