# Friend Circles

• 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

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

• @1337c0d3r yes, that's right.

• 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.

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

• 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.

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

• 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.

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

• 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?

• 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;
}

``````

• 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;
}

``````

• This post is deleted!

• 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)

``````

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