Question

A python question...

In your class, many students are friends. Let’s assume that two students sharing a friend must be friends themselves; in other words, if students 0 and 1 are friends and students 1 and 2 are friends, then students 0 and 2 must be friends. Using this rule, we can partition the students into circles of friends. To do this, implement a function networks() that takes two input arguments. The first is the number n of students in the class. We assume students are identified using integers 0 through n-1. The second input argument is a list of tuple objects that define friends. For example, tuple (0, 2) defines students 0 and 2 as friends. Function networks() should print the partition of students into circles of friends as illustrated: networks(5, [(0, 1), (1, 2), (3, 4)]) Social network 0 is {0, 1, 2} Social network 1 is {3, 4}

Answer 1

Screenshot of the code:

Code to copy:

# Find by path compression
def find(i):
   global arr
   while(arr[i]!=i):
       arr[i] = arr[arr[i]]
       i = arr[i]
   return i

# Union by size
def union(friend1, friend2):
   global arr, size
   if size[friend1]<size[friend2]:
       arr[friend1] = arr[friend2]
       size[friend2] += size[friend1]
   else:
       arr[friend2] = arr[friend1]
       size[friend1] += size[friend2]

def networks(n, friends_list):
   global arr, size
   # arr stores the one of friend val, arr[0] = 1 i.e. 1 is a friend of 0
   arr = [None]*n
   # Size of network
   size = [None]*n
   for i in range(n):
       # Everyone is a friend to himself
       arr[i] = i
       # Size of each group is 1
       size[i] = 1
   # For each tuple make union
   for friends in friends_list:
       union(friends[0], friends[1])
  
   network = []
   # Add unique values of arr to network as a single group
   for head in set(arr):
       network.append({head})

   for i in range(n):
       for group in network:
           # If friend of i is in current group then add i to that group
           if arr[i] in group:
               group.add(i)
   return network

# Function call
network = networks(5, [(0, 1), (1, 2), (3, 4)])
# Output
for i in range(len(network)):
   print('Social network ',i+1,': ',network[i])

output screenshot: