Problem p03157 (python)

Fixed submission:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rnk=[0]*(n+1)

    def Find_Root(self,x):
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.rnk[x]>self.rnk[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y]+=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

h,w=map(int,input().split())
g=[list(input()) for _ in range(h)]
uf=UnionFind(h*w)
dyx=[(1,0),(-1,0),(0,1),(0,-1)]
for i in range(h):
    for j in range(w):
        if g[i][j]==".":
            continue
        p=i*w+j
        for dy,dx in dyx:
            y=i+dy
            x=j+dx
            if 0<=y<h and 0<=x<w:
                if g[y][x]==".":
                    np=y*w+x
                    uf.Unite(p,np)

rt=[0]*(h*w)
for i in range(h*w):
    rt[i]=uf.Find_Root(i)

m=min(rt)
rt=list(map(lambda x:x-m, rt))
m=max(rt)
a=[[0,0] for _ in range(m+1)]
for i in range(h*w):
    y=i//w
    x=i%w
    if g[y][x]=="#":
        a[rt[i]][0]+=1
    else:
        a[rt[i]][1]+=1
ans=0
for i,j in a:
    ans+=i*j

print(ans)

Buggy submission (verdict: Runtime Error):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rnk=[0]*(n+1)

    def Find_Root(self,x):
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.rnk[x]>self.rnk[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y]+=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

h,w=map(int,input().split())
g=[list(input()) for _ in range(h)]
uf=UnionFind(h*w)
for i in range(h):
    for j in range(w-1):
        if g[i][j]!=g[i][j+1]:
            uf.Unite(i*3+j,i*3+j+1)

for j in range(w):
    for i in range(h-1):
        if g[i][j]!=g[i+1][j]:
            uf.Unite(i*3+j,(i+1)*3+j)

x=[]
for i in range(h*w):
    x.append(uf.Find_Root(i))

d=[[0,0] for _ in range(h*w)]
for i in range(h):
    for j in range(w):
        now=i*w+j
        nr=x[now]
        if g[i][j]=="#":
            d[nr][0]+=1
        else:
            d[nr][1]+=1
ans=0
for i in range(h*w):
    ans+=d[i][0]*d[i][1]
print(ans)

Buggy submission (verdict: Runtime Error):
h,w=map(int,input().split())
g=[list(input()) for _ in range(h)]

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rnk=[0]*(n+1)

    def Find_Root(self,x):
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.rnk[x]>self.rnk[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y]+=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

uf=UnionFind(h*w)

for i in range(h):
    for j in range(w):
        if j<w-1 and g[i][j]!=g[i][j+1]:
            uf.Unite(i*w+j,i*w+j+1)
        if i<h-1 and g[i][j]!=g[i+1][j]:
            uf.Unite(i*w+j,(i+1)*w+j)

kuro={}
siro={}

for i in range(h):
    for j in range(w):
        k=i*w+j
        if g[i][j]=="#":
            if uf.Find_Root(k) in kuro.keys():
                kuro[uf.Find_Root(k)]+=1
            else:
                kuro[uf.Find_Root(k)]=1
        else:
            if uf.Find_Root(k) in siro.keys():
                siro[uf.Find_Root(k)]+=1
            else:
                siro[uf.Find_Root(k)]=1

ans=0
for k in siro.keys():
    ans+=kuro[k]*siro[k]
print(ans)