Find friend groups

Tags: , ,

There are Nstudents in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if Ais a direct friend of B, and Bis a direct friend of C, then Ais an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students. For example,

Input: 
[[1,1,0,0,0,0],
 [1,1,0,0,0,0],
 [0,0,1,1,0,0],
 [0,0,1,1,1,0],
 [0,0,0,1,1,0],
 [0,0,0,0,0,1]
]
Output: 3

Thought process

When we talk about the connections or relationships, we immediately will think of graph data structure. The node is the person and the edge is the relationship between two persons. So, first, we have to figure out whether it will be a directed graph or an undirected graph. In this problem, the friendship is a mutual relationship, thus the graph is undirected.

When you are reading this problem, the concept of Strongly Connected Components(SCC) will come into your mind. Ok, we will discuss why? If A is a friend of B, B is a friend of C, then A will be a friend of C. What does it mean? A is indirectly connected to C. It means that every friend can reach every other friend through a path if they are directly or indirectly connected. So in this way, they are forming a strong group or circle, in which every vertex is connected directly or indirectly in its group/circle. Notice that all friends (both direct and indirect), who should be in one friend circle are also in one connected component​ in the graph. 

A particular group of friends is a single component. In this problem we are going to find out how many components are there in the graph.

friend groups

When you make a graph out of it. It will be like this(see below fig). It means there are 3 friends circles.

friend-circle

We can solve this problem using 2 methods: depth first search and disjoint set method

Using Depth first traversal method

Finding connected components for an undirected graph is very easy. We can do either BFS or DFS starting from every unvisited vertex, and we get all strongly connected components

1. Initialize all nodes as not visited.
2. Initialize variable count as 1.
3. for every vertex 'v'.
       (i) If 'v' is unvisited
            Call DFS(v)
            count=count+1
DFS(v)
1. Mark 'v' as visited.
2. Do following for every unvisited neighbor `u`
      recursively call DFS(u)

DFS based approach implementation

class Solution {
Public:
    void DFS(int node,vector<vector<int>> edges,vecto<bool>visited)
    {
        int i;
        visited[node]=true;
        for(int i=0;i<edges[node].size();i++)
        {
            if(edges[node][i]==1 && node!=i && visited[i]==false)
            {
                DFS(i,edges,visited);
            }
        }
    }

    //Main Method
    int findCircleNum(vector<vector<int>> edges) {
        int i,j;
        
        int n=edges.size();
        int count=0;
        vector<bool>visited(m);
        
        //mark all the nodes as unvisited
        for(i=0;i<n;i++)
        {
            visited[i]=false;
        }
        
        for(i=0;i<n;i++)
        {
            if(visited[i]==false)
            {
                DFS(i,edges,visited);
                count=count+1;
            }
        }
        
        return count;
    }
};

Complexity

  • Time Complexity: Since we just go along the edges and visit every node, it will be O(n).
  • Space Complexity: O(n), to store the visited nodes.

Using Disjoint Sets(Union Find)

So, how to think that this problem is solved by Disjoint Sets(union-find algorithm)?

 The answer is simple because we need to keep track of the set of elements(here friends) partitioned into a number of non-overlapping subsets. Disjoint Sets(Union Find) always do this work very efficiently. We will use the Union by Rank algorithm to solve this problem.

If you haven’t heard of the Disjoint Sets. Go to this link and read about it.

To join two nodes, we will compare the rank of parents of both nodes.

  • If the rank is equal, we can make any one of the parent’s node as a parent and increment the rank of the parent node by 1.
  • If the rank is not same, then we can make the parent whose rank is greater than other.

graph breadth first traversal application

 

Let’s start solving this.

Union(1,2): 1 is a parent of itself and 2 is parent of itself. As both of them have different parents, so we have to connect them, and we will any of the parent as root, in this case we chose 1 and make it a parent.

friend groups

Union(2,1): 1 is a parent of itself and 1 is a parent of 2, as both of them have the same parents, already joined.

Union(3,4) :3 is a parent of itself and 4 is a parent of itself. Both of them have different parents, we need to join them.

Union(4,3): 3 is parent of itself and 3 is the parent of 4. Both of them have the same parents, already joined.

Union(4,5):   3 is the parent node of 4 and 5 is the parent node of 5. Since parents are different, we have to compare the rank of the parents of both 4 and 5 nodes. 3 has higher rank then 5, it will be parent of 5 .(Used Path Compression) as shown in the below fig.

Union(5,4): As now, 4 and 5 have the same parents, already joined. Last is the node 6 which connected to itself. So, nothing to do there. At the end of this exercise, we found that there are three different sets in the graph, and that is our answer of number of groups of friends in this graph or matrix.

Disjoint set based approach implementation

class Solution {
public:
    class Node
    {
        public:
            int data;
            Node*parent;
            int rank=0;
    };
    //make a set with only one element.
    void make(int data)
    {
        Node*node=new Node();
        node->data=data;
        node->parent=node;
        node->rank=0;
        mapy[data]=node;
        return;
    }
    map<int,Node*> mapy;
    //To return the address of the particular node having data as `data` 
    Node*find(int data)
    {
        auto k=mapy.find(data);
        if(k==mapy.end())
        {
            //There is no any node created, create the node
            make(data);
            return mapy[data];
        }
        else
        {
            return mapy[data];
        }
        return NULL;
    }
    /*Find the representative(parent) recursively and does path compression  
    as well*/
    Node*parents(Node*node)
    {
        if(node->parent==node)
        {
            return node;
        }
        return node->parent = parents(node->parent);
    }
    //Main Method
    int findCircleNum(vector<vector<int>>edges) {
        int i,j;
        
        vector<int> v;
        int m=edges.size();
        int n=edges[0].size();
        for(i=0;i<m;i++)
        {
            for(j=0;j<n;j++)
            {
                if(edges[i][j]==1)
                {
                    int a=i;
                    int b=j;
                    
                    
                    Node*A=find(a);
                    Node*B=find(b);
            
                    Node*PA=parents(A);
                    Node*PB=parents(B);
            
                    if(PA==PB)
                    {
                    }
                    else
                    {
                        if(PA->rank>=PB->rank)
                        {
                            //increment rank if both sets have Same rank
                            PA->rank=(PA->rank==PB->rank)?PA->rank+1:PA->rank;
                            PB->parent=PA;
                        }
                        else
                        {
                            PA->parent=PB;
                        }
                    }
                    
                    }
                }
            }
        
        int number=0;
        for(auto k: mapy)
        {
            if(k.second->parent==k.second)
            {
                number=number+1;
            }
        }
        return number;
    }
};

Complexity

  • Time Complexity: For each of the edge, we need to find the parents  and do the union, which is O(mlogn).
  • Space Complexity: We used a map to store the parent information, O(n).

This post is contributed by Monika Bhasin