Friend Circles


  • 1
    N

    There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature, i.e., if A is friend of B and B is friend of C, then A is also friend of C. A friend circle is a group of students who are directly or indirectly friends.

    You are given a N×N − matrix M which consists of characters Y or N. If M[i][j]=Y, then ith and jth students are friends with each other, otherwise not. You have to print the total number of friend circles in the class.

    Each element of matrix friends will be Y or N.
    Number of rows and columns will be equal in the matrix.

    M[i][i]=Y, where 0≤i<N0≤i<N
    M[i][j] = M[j][i], where 0≤i<j<N

    Example 1
    Input:
    YYNN
    YYYN
    NYYN
    NNNY
    Output: 2

    Example 2
    Input
    YNNNN
    NYNNN
    NNYNN
    NNNYN
    NNNNY
    Output: 5


  • 0

    Interesting question! So the input will be given as a 2D boolean matrix am I right? (where Y = true and N = false)


  • 0
    N

    @1337c0d3r yes, that's right.


  • 1

    Since M[i][j] = M[j][i], it is an undirected graph. Each friend circle can be represented as one connected component in an undirected graph, which translates directly to this problem:

    Find the Number of Connected Components in an Undirected Graph

    The only difference is in the input format. This is given as a 2D boolean matrix, while the above problem's input is in edge-pairs representation.


  • 0
    N

    @1337c0d3r nice abstraction. I think they are quite similar


  • 0

    I love this problem more though. Although the problem description is longer, it has a nice application to finding friend circles, seems more interesting :D

    By the way, just like usual graph traversal problems, this can be solved using either BFS or DFS. Also it's a nice application of union find which is efficient in counting the number of connected components.


  • 0
    N

    thanks, I think the description of this problem has easier to understand background, but redundant input may get someone confused


  • 0

    By the way, a variation to this problem is to print a person's friend/friends of friends in the friend circle, which is very similar.


  • 0
    J

    I think I saw this exact same problem in one of Google's online coding challenges. Used union-find to solve it.


  • 0
    M

    Hello, I'm very interested in this topic and currently writing code to work this out. But I have a question: let's say a knows both b and c, and b knows c. I know a->b->c is a circle, but what about a directly knows c? Is a->c is an additional count or included in a->b->c circle when counting the total circles?


  • 0
    Y

    Here is my solution.

    #include <vector>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    int friend_circle(vector<string>  friends){
    	const int n(friends.size());
    	vector<bool> visited(n,false);
    	queue<int> bfs_queue;
    	bfs_queue.push(0);
    	visited[0] = true;
    	int reval(1);
    	while( !bfs_queue.empty() ) {
    		const int i = bfs_queue.front();
    		for (int j=0;j<n;++j) {
    			if (i!=j && friends[i][j]=='Y') {
    				friends[i][j] = friends[j][i] = 'N';
    				if(!visited[j]) { visited[j] = true; bfs_queue.push(j);}
    			}
    		}
    		bfs_queue.pop();
    
    		if(bfs_queue.empty()) {
    			auto iter = std::find(visited.begin(),visited.end(),false);
    			if (iter!=visited.end()) {
    				int index = iter-visited.begin();
    				bfs_queue.push(index);
    				visited[index] = true;
    				++ reval; // new connected components
    			}
    		}
    	}
    	return reval;
    }
    
    int main() {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
       int num;
        cin >> num;
        vector<string>  friends;
        string input_line;
        for (int i=0;i<num && cin;++i) {
            cin >> input_line;
            friends.push_back(input_line);
        };
        cout << friend_circle(friends) << endl;
        return 0;
    }
    
    

  • 0
    Y

    My second solution with union find.

    #include <cmath>
    #include <cstdio>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    class UnionFind {
    public:
    	UnionFind(int n) :m_num(n),m_ids(n,-1),m_count(n){
    		for (int i=0;i<m_num;++i) {
    			m_ids[i] = i;
    		}
    	}
    	bool is_connected(int node1, int node2) {return m_ids[node1] == m_ids[node2];}
    	int find(int node) {return m_ids[node];}
    	int get_count() {return m_count;}
    	// If two nodes are in different disjoint-set, union their set together.
    	// Here we go through all the nodes, if any node's id is the same as node2,
    	// which means it is at the same disjoint-set with node2, we reset its id value
    	// to be the same as node1.
    	void union_set(int node1,int node2) {
    		const int id1 = m_ids[node1], id2 = m_ids[node2];
    		if (id1 != id2) {
    			for (int i=0;i<m_num;++i) {
    				if (m_ids[i] == id2) m_ids[i] = id1;
    			}
    			-- m_count;
    		}
    	}
    private:
    	int m_num; // how many nodes in total
    	int m_count; // how many disjoint-set 
    	vector<int> m_ids; // ID of each node,ID is the representative of each disjoint-set
    };
    int friend_circle(vector<string>  friends){
    	const int n(friends.size());
    	UnionFind uf(n);
    	for (int i=0;i<n;++i) {
    		for (int j=0;j<n;++j) {
    			if (friends[i][j]=='Y' && !uf.is_connected(i,j)) {
    				uf.union_set(i,j);
    			}
    		}
    	}
    	return uf.get_count();
    }
    int main() {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
        int num;
        cin >> num;
        vector<string>  friends;
        string input_line;
        for (int i=0;i<num && cin;++i) {
            cin >> input_line;
            friends.push_back(input_line);
        };
        cout << friend_circle(friends) << endl;
        return 0;
    }
    
    

  • 0
    A
    This post is deleted!

  • 0
    E

    Python 3.6 solution

    def traverse_friend_circle(node: int, friends: [[int]]) -> set:
        """
        Given a starting node, go through all of his friends and their friends and their and etc...,
            while storing each node
        """
        from collections import deque
    
        friend_circle = {node}
        friends_to_visit = deque()
        friends_to_visit.append(node)
    
        while friends_to_visit:
            node = friends_to_visit.popleft()
    
            for friend, are_friends in enumerate(friends[node]):
                if are_friends and friend not in friend_circle:
                    friend_circle.add(friend)
                    friends_to_visit.append(friend)
    
        return friend_circle
    
    
    CONNECTION_TO_BOOL = {
        'Y': True,
        'N': False
    }
    n = int(input())
    # Build a boolean matrix
    matrix = []
    for _ in range(n):
        matrix.append([CONNECTION_TO_BOOL[conn] for conn in input()])
    
    # the number of friend circles is the number of components in the graph
    
    visited = set()
    friend_circle_count = 0
    for node in range(n):
        if node not in visited:
            friend_circle: {int} = traverse_friend_circle(node, matrix)
            visited.update(friend_circle)
            friend_circle_count += 1
    
    print(friend_circle_count)
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.