From 3e8bb5f0c3285affdad016cc72a511d1d6fc4257 Mon Sep 17 00:00:00 2001
From: Aditya Naik
Date: Sat, 12 May 2018 21:07:43 -0400
Subject: roads starting core algo

---
 10009/roads.cpp | 62 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 10009/roads.in  | 12 +++++++++++
 2 files changed, 74 insertions(+)
 create mode 100644 10009/roads.cpp
 create mode 100644 10009/roads.in

(limited to '10009')

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;
+	} 	
+    }
+}
+
diff --git a/10009/roads.in b/10009/roads.in
new file mode 100644
index 0000000..b15368d
--- /dev/null
+++ b/10009/roads.in
@@ -0,0 +1,12 @@
+1
+7 3
+Rome Turin
+Turin Venice
+Turin Genoa
+Rome Pisa
+Pisa Florence
+Venice Athens
+Turin Milan
+Turin Pisa
+Milan Florence
+Athens Genoa	
\ No newline at end of file
-- 
cgit v1.2.3