Problem p02762 (python)

Fixed submission:
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(0, n+1)}
sizes = {i:1 for i in range(0, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, u):
	if parent[u] != u: 
		parent[u] = f(parent, parent[u])
	return parent[u]

for a,b in friendships:
	if a == b: continue

	pa,pb = f(parent, a), f(parent, b)
	
	adj[a].add(b)
	adj[b].add(a)

	if pa != pb:
		if sizes[pa] >= sizes[pb]:
			parent[pb] = pa
			sizes[pa] += sizes[pb]
		else:
			parent[pa] = pb
			sizes[pb] += sizes[pa]

for c,d in disses:
	pc,pd = f(parent, c), f(parent, d)
	if (pc == pd):
		hd[c] += 1
		hd[d] += 1
"""
hd[u] = k
u has k disses in its connected component
"""

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

Buggy submission (verdict: Runtime Error):
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(0, n+1)}
sizes = {i:1 for i in range(0, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, u):
	if parent[u] != u: 
		parent[u] = f(parent, parent[u])
	return parent[u]

for a,b in friendships:
	if a != b:
		pa,pb = f(parent, a), f(parent, b)
		
		adj[a].add(b)
		adj[b].add(a)

		if pa != pb:
			parent[pb] = pa
			sizes[pa] += sizes[pb]

for c,d in disses:
	pc,pd = f(parent, c), f(parent, d)
	if (pc == pd):
		hd[c] += 1
		hd[d] += 1
"""
hd[u] = k
u has k disses in its connected component
"""

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

Buggy submission (verdict: Runtime Error):
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(0, n+1)}
sizes = {i:1 for i in range(0, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, a):
	if parent[a] != a: parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	if a != b:
		pa,pb = f(parent, a), f(parent, b)
		
		adj[a].add(b)
		adj[b].add(a)

		if pa != pb:
			parent[pb] = pa
			sizes[pa] += sizes[pb]

for c,d in disses:
	pa,pb = f(parent, c), f(parent, d)
	if (pa == pb):
		hd[c] += 1
		hd[d] += 1
"""
hd[u] = k
u has k disses in its connected component
"""

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

Buggy submission (verdict: Runtime Error):
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(1, n+1)}
sizes = {i:1 for i in range(1, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, a):
	if parent[a] != a: parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	if a != b:
		pa,pb = f(parent, a), f(parent, b)
		
		adj[a].add(b)
		adj[b].add(a)

		if pa != pb:
			parent[pb] = pa
			sizes[pa] += sizes[pb]

for c,d in disses:
	pa,pb = f(parent, c), f(parent, d)
	if (d not in adj[c]) and  (pa == pb):
		hd[c] += 1
		hd[d] += 1
"""
hd[u] = k
u has k disses in its connected component
"""

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

Buggy submission (verdict: Runtime Error):
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(1, n+1)}
sizes = {i:1 for i in range(1, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, a):
	if parent[a] != a: parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	pa,pb = f(parent, a), f(parent, b)
	
	adj[a].add(b)
	adj[b].add(a)

	if pa != pb:
		parent[pb] = pa
		sizes[pa] += sizes[pb]

for c,d in disses:
	pa,pb = f(parent, c), f(parent, d)
	if (d not in adj[c]) and  (pa == pb):
		hd[c] += 1
		hd[d] += 1

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

Buggy submission (verdict: Runtime Error):
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(1, n+1)}
sizes = {i:1 for i in range(1, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, a):
	if parent[a] != a: parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	pa,pb = f(parent, a), f(parent, b)
	
	adj[a].add(b)
	adj[b].add(a)

	if pa != pb:
		parent[pb] = pa
		sizes[pa] += sizes[pb]

for c,d in disses:
	pa,pb = f(parent, c), f(parent, d)
	if pa == pb:
		hd[c] += 1
		hd[d] += 1

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

Buggy submission (verdict: Runtime Error):
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(1, n+1)}
sizes = {i:1 for i in range(1, n+1)}

hd = {i:0 for i in range(1, n+1)}

adj = collections.defaultdict(set)

def f(parent, a):
	if parent[a] != a: parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	pa,pb = f(parent, a), f(parent, b)
	adj[a].add(b)
	adj[b].add(a)
	if pa != pb:
		parent[pb] = pa
		sizes[pa] += sizes[pb]

for c,d in disses:
	pa,pb = f(parent, c), f(parent, d)
	if pa == pb:
		hd[c] += 1
		hd[d] += 1

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

Buggy submission (verdict: Runtime Error):
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]
parent = {i:i for i in range(1, n+1)}
sizes = {i:1 for i in range(1, n+1)}
counts = {i:0 for i in range(1, n+1)}
howmanydisses = {i:0 for i in range(1, n+1)}
adj = collections.defaultdict(set)
def f(parent, a):
	if parent[a] != a:
		parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	pa,pb = f(parent, a), f(parent, b)
	counts[a] +=1
	counts[b] +=1
	adj[a].add(b)
	adj[b].add(a)
	if pa != pb:
		parent[pb] = pa
		sizes[pa] += sizes[pb]

for a,b in disses:
	pa,pb = f(parent, a), f(parent, b)
	if pa == pb:
		if b not in adj[a]:
			howmanydisses[a] += 1
			howmanydisses[b] += 1

print ' '.join([str(sizes[f(parent,a)] - counts[a] - howmanydisses[a] - 1)  for a in range(1, n+1)])

Buggy submission (verdict: Runtime Error):
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]
parent = {i:i for i in range(1, n+1)}
sizes = {i:1 for i in range(1, n+1)}
counts = {i:0 for i in range(1, n+1)}
howmanydisses = {i:0 for i in range(1, n+1)}

def f(parent, a):
	if parent[a] != a:
		parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	pa,pb = f(parent, a), f(parent, b)
	counts[a] +=1
	counts[b] +=1
	if pa != pb:
		parent[pb] = pa
		sizes[pa] += sizes[pb]

for a,b in disses:
	pa,pb = f(parent, a), f(parent, b)
	if pa == pb:
		howmanydisses[a] += 1
		howmanydisses[b] += 1

print ' '.join([str(sizes[f(parent,a)] - counts[a] - howmanydisses[a] - 1)  for a in range(1, n+1)])