Problem p03855 (python)

Fixed submission:
#Union-Find木の構築
import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        aT = [0]*(iN+1)
        for p,q in a:
            rp = getRoot(aT,p)
            rq = getRoot(aT,q)
            thisRoot = max(rp,rq,q)
            aT[p] = thisRoot
            aT[q] = thisRoot
            aT[rp] = thisRoot #これで Union してるつもり
            aT[rq] = thisRoot
        return aT
    def getRoot(a,i): #find みんな小さい方に合わせるならデカい方に合わせてみよう
        if a[i] == i or a[i] == 0:
            if a[i] == 0 : a[i] = i
            return i
        elif i < a[i] :
            a[i] = getRoot(a,a[i])
            return a[i]
    #   else:
    #       print("! ",i,a[i])

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        # いやはやこんなもんもキーになるのか。
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()

Buggy submission (verdict: Runtime Error):
#Union-Find木の構築
import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        aT = [0]*(iN+1)
        for p,q in a:
            #if p > q :
            #   p,q = q,p
            thisroot = max(aT[q],aT[p],q) #試しにデカい方に合わせる
            if p <= aT[q] < thisroot:  #2個づつ来るからこんなんでいいだろ
                aT[aT[q]] = thisroot
            if p <= aT[p] < thisroot:
                aT[aT[p]] = thisroot
            aT[q] = thisroot
            aT[p] = thisroot
        return aT
    def getRoot(a,i):
        if a[i] == i or a[i] == 0:
            if a[i] == 0 : a[i] = i
            return i
        elif i < a[i] :
            a[i] = getRoot(a,a[i])
            return a[i]
        else:
        #   print("! ",i,a[i])

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        # いやはやこんなもんもキーになるのか。
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()

Buggy submission (verdict: Runtime Error):
mport sys
sys.setrecursionlimit(10**5)
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    a道 = aD[0:iK]
    a鉄道 = aD[iK:]

    d道 = {}
    d鉄道 = {}
#   for i in range(1,iN+1):
#       d道[i] = {i}
#       d鉄道[i] ={i}
    def fMakeSet(d,x,y):
        if x in d:
            d[x].add(y)
        else:
            d[x] = {y}

    for p,q in a道:
        #d道[p].add(q)
        #d道[q].add(p)
        fMakeSet(d道,q,p)
        fMakeSet(d道,p,q)
    for r,s in a鉄道:
        fMakeSet(d鉄道,r,s)
        fMakeSet(d鉄道,s,r)

    def fdfs(d,iS):
        dsVisited=set()
        def digRoute(iT):
            dsVisited.add(iT)
            if iT in d:
                for i in d[iT] - dsVisited:
                    #dsVisited.add(i)
                    digRoute(i)
        digRoute(iS)
        return dsVisited
    def buildGroup(d):
        gl = {}
        gidx = {}
        v = set()
        iC = 0
        for i in range(1,iN+1):
            if i in v:
                continue
            else:
                dsList = fdfs(d,i)
                for i in dsList:
                    gidx[i] = iC
                gl[iC]=dsList
                iC += 1
                v = v | dsList
        return (gl,gidx)
    dg鉄道,idxdg鉄道 = (buildGroup(d鉄道))
    dg道,idxdg道 = (buildGroup(d道))
    ak鉄道 = dg鉄道.keys()
    ak道 = dg道.keys()
    aM = [[ None for _ in range(len(ak道))] for _ in range(len(ak鉄道))]
    for i in ak鉄道:
        for j in ak道:
            aM[i][j]=len(dg鉄道[i] & dg道[j])
    aRet = []
    for i in range(1,iN+1):
        aRet.append(str(aM[idxdg鉄道[i]][idxdg道[i]]))
    print( " ".join(aRet))
解()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionliit(10**5)
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    a道 = aD[0:iK]
    a鉄道 = aD[iK:]

    d道 = {}
    d鉄道 = {}
    for i in range(1,iN+1):
        d道[i] = {i}
        d鉄道[i] ={i}

    for p,q in a道:
        d道[p].add(q)
        d道[q].add(p)
    for r,s in a鉄道:
        d鉄道[r].add(s)
        d鉄道[s].add(r)

    def fdfs(d,iS):
        dsVisited=set()
        def digRoute(iT):
            for i in d[iT] - dsVisited:
                dsVisited.add(i)
                digRoute(i)
        digRoute(iS)
        return dsVisited

    aRet = []
    for i in range(1,iN+1):
        aRet.append(str(len(fdfs(d道,i) & fdfs(d鉄道,i))))
    print( " ".join(aRet))
解()

Buggy submission (verdict: Runtime Error):
import sys
iN,iK,iL = [int(_) for _ in input().split()]
aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
a道 = aD[0:iK]
a鉄道 = aD[iK:]

d道 = {}
d鉄道 = {}
for i in range(1,iN+1):
    d道[i] = {i}
    d鉄道[i] ={i}

for p,q in a道:
    d道[p].add(q)
    d道[q].add(p)
for r,s in a鉄道:
    d鉄道[r].add(s)
    d鉄道[s].add(r)

def fdfs(d,iS):
    dsVisited=set()
    def digRoute(iT):
        for i in d[iT] - dsVisited:
            dsVisited.add(i)
            digRoute(i)
    digRoute(iS)
    return dsVisited

aRet = []
for i in range(1,iN+1):
    aRet.append(str(len(fdfs(d道,i) & fdfs(d鉄道,i))))
print( " ".join(aRet))