Ant book in python: Sec. 2-5 Graph

page93: Bipartite graph judgment

from Graph import join_dic  #See the preparation article for the contents
from Graph import d_to_ud  #See the preparation article for the contents

#############Make a directed graph###########
N = int(input())
graph = {}
while 1:
    edge = input()
    if edge == "":
        break

    edge = list(map(int, edge.split()))
    dic = {edge[0]: edge[1]}
    graph = join_dic(graph, dic)
##########################################

graph = d_to_ud(graph)   ###I want to process it recursively, so make it an undirected graph

for i in graph:
    if isinstance(graph[i], list):
        continue
    else:
        graph[i] = [graph[i]]   #### for i in graph[hoge]So that the processing can be unified with, 

#Postscript) if not isinstance(graph[i],list)I should have done it.

color = (N) * [0]

def coloring(start, col):  ##Can you paint the connected component to which node start belongs?

    color[start] = col

    for i in graph[start]:
        if color[i] == col:  ##Out if adjacent sites are the same color
            return False
        if color[i] == 0 and (not coloring(i, -col)):　 ##If the adjacent site is colorless, start painting from there with the opposite color to start
            return False

    return True


def solve():
    for i in graph:
        if color[i] == 0:
            if not coloring(i, 1):    ##Can you start from i and apply the connecting component?
                print("No")
                return 0

    print("Yes")
    return 0


solve()

input:

4  
0 1
1 2
2 3
0 3

output:

Yes

input:

3
0 1
1 2
2 0

output:

No

Since the graph is not always concatenated, we need to look at all nodes.

page95: Bellman-Ford method

input:

3

0 1 1
1 2 1
0 2 3

0

2

output:

2

import mygraph

print("number of nodes")
N = int(input())

print("input graph")
graph = mygraph.WeightedGraph()

while 1:

    inputline = input()

    if inputline == "":
        break

    inputline = list(map(int, inputline.split()))

    graph.join(inputline[0], inputline[1], inputline[2])

graph = graph.undirected()


for node in graph:
    if not isinstance(graph[node][0], list):
        graph[node] = [graph[node]]

print("Start?")
startpos = int(input())
print("Goal?")
goalpos = int(input())


dp = N * [float("INF")]


while 1:

    update = False

    dp[startpos] = 0

    for from_node in graph:

        neighbors = graph[from_node]

        for [to_node, weight] in neighbors:

            if dp[from_node] != float("INF") and dp[to_node] > dp[from_node] + weight:

                dp[to_node] = dp[from_node] + weight

                update = True

    if not update:
        break

print(dp[goalpos])

mygraph.py is a classized version written by @sishiracamus in the comments of the preparation article.