summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--sources/bfs.py39
1 files changed, 39 insertions, 0 deletions
diff --git a/sources/bfs.py b/sources/bfs.py
new file mode 100644
index 0000000..5d28baa
--- /dev/null
+++ b/sources/bfs.py
@@ -0,0 +1,39 @@
+# Uses python3
+
+import sys
+import queue
+
+
+def bfs(adj, s, dist):
+ q = queue.Queue()
+ q.put(s)
+
+ while not q.empty():
+ u = q.get()
+ for i in adj[u]:
+ if dist[i] == -1:
+ q.put(i)
+ dist[i] = dist[u] + 1
+
+
+def distance(adj, s, t):
+ dist = [-1] * len(adj)
+ dist[s] = 0
+
+ bfs(adj, s, dist)
+
+ return dist[t]
+
+
+if __name__ == '__main__':
+ input = sys.stdin.read()
+ data = list(map(int, input.split()))
+ n, m = data[0:2]
+ data = data[2:]
+ edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2]))
+ adj = [[] for _ in range(n)]
+ for (a, b) in edges:
+ adj[a - 1].append(b - 1)
+ adj[b - 1].append(a - 1)
+ s, t = data[2 * m] - 1, data[2 * m + 1] - 1
+ print(distance(adj, s, t))