Using Minimum Spanning Tree to Solve the Graph-releated Problem: Learning Languages

The problem is from codeforces: http://www.codeforces.com/contest/278/problem/C

The problem is graph-related and can be solved by many approaches. There is one exception case that you need to pay attention to: If at the beginning, everybody knows no languages, we have to add a n edges, the answer is n.

If an employee knows a language initially, there will be an edge between the corresponding nodes. The answer would be the number of initially connected components, containing at least one employee, minus one. One solution is to add the minimal number of edges in such a way, that all the n employees will be in the same connected component.

In [here], the data structure Disjoint Sets (DS) is illustrated in Python. With Disjoint Set, it is easily possible to solve this problem.

The python solution below solves the Minimum Spanning Tree using the Disjoint Set.

#!/usr/bin/env python

father = [i for i in range(101)]
rank = [0] * 101

def find(x):
    global father
    px = x
    while px != father[px]:
        px = father[px] # trace to root
    while x != px:
        i = father[x]
        father[x] = px # link to root
        x = i
    return px

def same(x, y):
    return find(x) == find(y)

def union(x, y):
    global father, rank
    x = find(x)
    y = find(y)
    if x == y: return  # same set
    if rank[x] > rank[y]:
        father[y] = x
    else:
        if rank[x] == rank[y]:
            rank[y] += 1 # update the rank
        father[x] = y

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

arr = []
for i in xrange(n):
    s = map(int, raw_input().split())
    arr.append(s[1:])

cnt = 0
for i in xrange(n):
    for j in xrange(i):
        for k in arr[j]:
            if k in arr[i]:
                union(i, j)

for i in xrange(n):
    if len(arr[i]) == 0:
        cnt += 1
        continue
    for j in xrange(i):
        if len(arr[j]) == 0:
            continue
        if (not same(i, j)):
            cnt += 1
            union(i, j)
print cnt

The approach is straightforward, connecting two components and increment the answer by one.

We can also use DFS (Depth-First-Search) in this case.

from __future__ import print_function
import sys
sys.setrecursionlimit(2000)
n, m = map(int, raw_input().split())

lang = []
for i in range(n):
    k = raw_input().split()[1:]
    lang.append(set(k))

if not any(lang):
    print(n)
    exit(0)

edges = [[] for i in range(n)]

for i in range(n):
    for j in range(n):
        if lang[i] & lang[j]:
            edges[i].append(j)
            #edges[j].append(i)

langs = [0] * n

def dfs(start):
    langs[start] = 1
    for i in edges[start]:
        if not langs[i]:
            dfs(i)

ans = 0
for i in range(n):
    if not langs[i]:
        ans += 1
        dfs(i)

print(ans - 1)

Or even a shorter implementation using set:

R = lambda:map(int,raw_input().split())
n, m = R()
G = range(n)
r = map(int, G)
def rt(x):
  if x != r[x]: r[x] = rt(r[x])
  return r[x]
e=[0] * n
for i in G: e[i] = set(R()[1:])
for i in G:
  for j in G[:i]:
    u = rt(j)
    if e[u].intersection(e[i]):
      r[u] = i
      e[i] = e[i].union(e[u])
print sum(1 for i in G if i == rt(i) or not e[i]) - (sum(map(len, e)) > 0)

–EOF (The Ultimate Computing & Technology Blog) —