diff options
| -rw-r--r-- | sources/bipartite.py | 50 |
1 files changed, 50 insertions, 0 deletions
diff --git a/sources/bipartite.py b/sources/bipartite.py new file mode 100644 index 0000000..bbc1724 --- /dev/null +++ b/sources/bipartite.py @@ -0,0 +1,50 @@ +# Uses python3 + +import sys +import queue + + +def bfsBipartiteCheck(adj, s): + if len(adj[s]) == 0: + return True + + dist = [-1] * len(adj) + dist[s] = 0 + + 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) + if dist[u] == 0: + dist[i] = 1 + if dist[u] == 1: + dist[i] = 0 + else: + if dist[i] == dist[u]: + return False + return True + + +def bipartite(adj): + bipartitite_check_nodes = bfsBipartiteCheck(adj, 0) + if bipartitite_check_nodes: + return 1 + else: + return 0 + + +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) + print(bipartite(adj)) |