AOJ 1163: Cards

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1163&lang=jp

概要
2以上10000000未満の数値が書かれた青と赤のカードが複数与えられる。2以上の公約数を持つような赤と青のペアは最大でいくつ作れるか。

解法
二部マッチング。アリ本p197をそのまま写しました。
入力が特殊な為、言語によっては注意が必要です。
enumerateがstartを指定できることを知った。幸せ。
20秒強掛かったので直すべき箇所があるかもしれません。

ソースコード

from fractions import gcd
 
V = 1002
G = []
visited = []
match = []
 
def add_edge(u,v):
    G[u].append(v)
    G[v].append(u)
 
def dfs(v):
    visited[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not visited[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True
 
def bipartite_matching():
    global match,visited
    res = 0
    match = [-1]*V
    for v in xrange(V):
        if match[v] < 0:
            visited = [False]*V
            if dfs(v):
                res += 1
    return res
 
while True:
    m,n = map(int,raw_input().split())
    if (m,n) == (0,0):
        break
    V = m+n+2
    G = [[] for _ in xrange(V)]
    visited = [True] * V
    data = []
    while len(data) < n+m:
        data += map(int,raw_input().split()) 
    for i,b in enumerate(data[:m]):
        for j,r in enumerate(data[m:],m):
            if gcd(b,r) != 1:
                add_edge(i,j)
    print bipartite_matching()