Influenced by Social Networking sites, Rahul launches his own site Friendsbook. Each user in Friendsbook is given a unique number, first user being numbered 1. There are N users in Friendsbook numbered from 1 to N. In Friendsbook, i th user can make j th user his friend without becoming his friend himself, i.e. in Friendsbook, there is a one-way link rather than a two-way link as in Facebook. Moreover i th user can make j th user his friend iff i>j. Also one user should have no more and no less than one friend except user 1 who will have no friend. Rahul wants to modify Friendsbook and find out whether one user is somehow linked to some other user. Help Rahul do so.
Print all possible connections between the users in the following format: 
4 2 2 means 4 is linked to 2 via 2 connections.
5 2 3 means 5 is linked to 2 via 3 connections, and so on.
The order of display should be as follows:
Print all possible connections starting from user 2 to user N with other users starting from 1 to The Current User Number - 1. In case one user is not connected at all with another user, that connection should not be printed.
 
Example 1:
Input: 
N = 3
arr[] = {1, 2}
Output:
2 1 1 3 1 2 3 2 1
Explanation:
2 is directly linked to 1 and hence 2 is
linked to 1 via 1 connection. 3 is directly
linked to 2 which in turn is directly
linked to 1. Hence 3 is linked to 1 via 
2 connections and to 2 via 1 connection.
Example 2:
Input: 
N = 3
arr[] = {1, 1}
Output:
2 1 1 3 1 1
Explanation:
Both 2 and 3 are directly linked to 1.
Hence both 2 and 3 are linked to 1 via
1 connection.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function socialNetwork() which takes an Integer N and an array arr[] of N-1 integers as input and returns s string representing the answer.
 
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
 
Constraints:
2 <= N <= 500
1 <= arr[i] <= i

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def socialNetwork(self, arr, N):
        # code here 

Solutions:
class Solution:

	def socialNetwork(self, arr, N):
		links = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
		for i in range(N - 1):
			links[i + 2][arr[i]] = 1
			for j in range(1, arr[i]):
				if links[arr[i]][j] != 0:
					links[i + 2][j] = links[i + 2][arr[i]] + links[arr[i]][j]
		ans = []
		for i in range(2, N + 1):
			for j in range(1, i):
				if links[i][j] != 0:
					ans.append(i)
					ans.append(j)
					ans.append(links[i][j])
		return ' '.join((str(a) for a in ans))
		1 < 2
		1 < 3 < 4


def transitiveclosureutil(graph, v, s, trans, num):
	trans[v][s] = num
	if v == s:
		trans[v][s] = 1
	for i in graph[s]:
		if not trans[v][i]:
			transitiveclosureutil(graph, v, i, trans, num + 1)

def transitiveclosure(graph):
	trans = [[0] * len(graph) for i in range(len(graph))]
	for i in range(2, len(graph)):
		transitiveclosureutil(graph, i, i, trans, 0)
	return trans

class Solution:

	def socialNetwork(self, arr, N):
		graph = [[] for i in range(N + 1)]
		for i in range(len(arr)):
			graph[i + 2].append(arr[i])
		trans = transitiveclosure(graph)
		res = ''
		for i in range(2, N + 1):
			for j in range(N + 1):
				if i != j and trans[i][j] != 0:
					s = str(i) + ' ' + str(j) + ' ' + str(trans[i][j]) + ' '
					res += s
		return res


class Solution:

	def socialNetwork(self, arr, N):
		parent = [-1 for i in range(N + 2)]
		visited = [False for i in range(N + 2)]

		def parentsss(v, count, origin, temp):
			if parent[v] == 1:
				temp.append([origin, 1, count])
				return 0
			else:
				temp.append([origin, parent[v], count])
				parentsss(parent[v], count + 1, origin, temp)

		def create_output():
			output = []
			for i in range(len(parent)):
				if parent[i] == -1:
					continue
				else:
					temp = []
					parentsss(i, 1, i, temp)
					temp.reverse()
				for i in temp:
					output.extend(i)
			return output
		for i in range(N - 1):
			parent[i + 2] = arr[i]
		output = create_output()
		output = list(map(str, output))
		output = ' '.join(output)
		return output


class Solution:

	def dfs(self, v, visited, adj, path):
		visited[v] = True
		if v in adj:
			for u in adj[v]:
				if not visited[u]:
					path.append(u)
					self.dfs(u, visited, adj, path)
		visited[v] = False

	def socialNetwork(self, arr, N):
		ans = ''
		(adj, visited) = ({}, {})
		for i in range(1, N + 1):
			visited[i] = False
			if i != N:
				adj[i + 1] = [arr[i - 1]]
		for i in range(2, N + 1):
			path = []
			self.dfs(i, visited, adj, path)
			while len(path) > 0:
				ans += str(i) + ' ' + str(path[-1]) + ' ' + str(len(path)) + ' '
				path.pop()
		return ans