summaryrefslogtreecommitdiff
path: root/sources
diff options
context:
space:
mode:
authorHaidong Ji2020-07-16 21:51:36 -0500
committerHaidong Ji2020-07-16 21:51:36 -0500
commitf83de5ee51c1985a5ee98a587416af142cbd1e2d (patch)
tree55a6aa7903c537e4ec9399b2d42da01e48226323 /sources
parent7e295af56cffda1dc0a65e3f905e58509dcafebc (diff)
Graph BFS distance done.
Diffstat (limited to 'sources')
-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))