- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a a friends list, where friends[i] is a list of people i is friends with. The connection of friendships are two-way. And each person is friend with themselves and two people are in a friend group as long as there is some path of mutual friends connecting them. We have to find the total number of friend groups.

So, if the input is like friends = [[0, 1, 5],[1, 0],[2],[3, 4],[4, 3],[5, 0]], then the output will be 3, as The three friend groups are as below −

To solve this, we will follow these steps −

- nodes := size of friends
- visited := a list of size same as nodes and fill with False
- ans := 0
- Define a function dfs() . This will take vertex, visited
- visited[vertex] := True
- for each nei in friends[vertex], do
- if visited[nei] is false, then
- dfs(nei, visited)

- if visited[nei] is false, then
- From the main method, do the following −
- for i in range 0 to nodes, do
- if visited[i] is false, then
- dfs(i, visited)
- ans := ans + 1

- if visited[i] is false, then
- return ans

Let us see the following implementation to get better understanding −

class Solution: def solve(self, friends): nodes = len(friends) visited = [False for _ in range(nodes)] ans = 0 def dfs(vertex, visited): visited[vertex] = True for nei in friends[vertex]: if not visited[nei]: dfs(nei, visited) for i in range(nodes): if not visited[i]: dfs(i, visited) ans += 1 return ans ob = Solution() friends = [ [0, 1, 5], [1, 0], [2], [3, 4], [4, 3], [5, 0] ] print(ob.solve(friends))

[[0, 1, 5], [1, 0], [2], [3, 4], [4, 3], [5, 0] ]

3

- Related Questions & Answers
- Program to count number of unhappy friends in Python
- Program to find maximum number of balanced groups of parentheses in Python
- Program to find minimum number of monotonous string groups in Python
- Program to find maximum number of groups getting fresh donuts in Python
- Program to group a set of points into k different groups in Python
- Program to find minimum number of groups in communication towers in C++?\n
- Program to find maximum number of K-sized groups with distinct type items are possible in Python
- Program to find super digit of a number in Python
- Find groups of strictly increasing numbers in a list in Python
- Program to find number of values factors of two set of numbers
- Program to find number of nodes in a range in Python
- Python program to find better divisor of a number
- Python program to find factorial of a large number
- Get the number of open connections in MongoDB?
- Find sum of even factors of a number in Python Program

Advertisements