# 547.friend-circles-en

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature.

For example, if A is a direct friend of B, and B is a direct friend of C, then A is 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.

Example 1:

Input:

[[1,1,0],

[1,1,0],

[0,0,1]]

Output: 2

Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.

The 2nd student himself is in a friend circle. So return 2.

Example 2:

Input:

[[1,1,0],

[1,1,1],

[0,1,1]]

Output: 1

Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,

so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

Note:

N is in range [1,200].

M[i][i] = 1 for all students.

If M[i][j] = 1, then M[j][i] = 1.

We can view a given matrix as Adjacency Matrix of a graph. In this case, this problem become to find number of connected components in a undirected graph.

For example, how to transfer Adjacency Matrix into a graph problem. As below pic:

adjacency matrix

Connected components in a graph problem usually can be solved using

*DFS*,*BFS*,*Union-Find*.Below we will explain details on each approach.

- 1.Do DFS starting from every node, use
`visited`

array to mark visited node. - 2.For each node DFS, visit all its directly connected nodes.
- 3.For each node DFS, DFS search will search all connected nodes, thus we count one DFS as one connected component.

as below pic show

*DFS*traverse process:friend circle DFS

*Time Complexity:*`O(n*n) - n is the number of students, traverse n*n matrix`

*Space Complexity:*`O(n) - visited array of size n`

- 1.Start from one node, visit all its directly connected nodes, or visit all nodes in the same level.
- 2.Use
`visited`

array to mark already visited nodes. - 3.Increment count when start with a new node.

as below pic show

*BFS*(Level traverse) traverse process:friend circle BFS

*Time Complexity:*`O(n*n) - n is the number of students, traverse n*n matrix`

*Space Complexity:*`O(n) - queue and visited array of size n`

Determine number of connected components, Union Find is good algorithm to use.

Use

`parent`

array, for every node, all its directly connected nodes will be `union`

, so that two connected nodes have the same parent. After traversal all nodes, we just need to calculate the number of different values in `parent`

array.For each union, total count minus 1, after traversal and union all connected nodes, simply return counts.

Here use

**weighted-union-find**to reduce`union`

and `find`

methods operation time.To know more details and implementations, see further reading lists.

as below Union-Find approach process:

friend circle union-find

Note:here using weighted-union-find to avoid Union and Find take`O(n)`

in the worst case.

*Time Complexity:*`O(n*n*log(n) - traverse n*n matrix, weighted-union-find, union and find takes log(n) time complexity.`

*Space Complexity:*`O(n) - parent and rank array of size n`

- 1.Transform Adjacency matrix into Graph
- 2.Notice that it actually is to find number of connected components problem.
- 3.Connected components problem approaches (DFS, BFS, Union-Find).

*Java code*-

**DFS**

class FindCirclesDFS {

public int findCircleNumDFS(int[][] M) {

if (M == null || M.length == 0 || M[0].length == 0) return 0;

int n = M.length;

int numCircles = 0;

boolean[] visited = new boolean[n];

for (int i = 0; i < n; i++) {

if (!visited[i]) {

dfs(M, i, visited, n);

numCircles++;

}

}

return countCircle;

}

private void dfs(int[][] M, int i, boolean[] visited, int n) {

for (int j = 0; j < n; j++) {

if (M[i][j] == 1 && !visited[j]) {

visited[j] = true;

dfs(M, j, visited, n);

}

}

}

}

*Java code*-

**BFS**

class FindCircleBFS {

public int findCircleNumBFS(int[][] M) {

if (M == null || M.length == 0) return 0;

int numCircle = 0;

int n = M.length;

boolean[] visited = new boolean[n];

Queue<Integer> queue = new LinkedList<>();

for (int i = 0; i < n; i++) {

// already visited, skip

if (visited[i]) continue;

queue.add(i);

while (!queue.isEmpty()) {

int curr = queue.poll();

visited[curr] = true;

for (int j = 0; j < n; j++) {

if (M[curr][j] == 1 && !visited[j]) {

queue.add(j);

}

}

}

numCircle++;

}

return numCircle;

}

}

*Java code*-

**Union-Find**

class FindCircleUF {

public int findCircleNumUF(int[][] M) {

if (M == null || M.length == 0 || M[0].length == 0) return 0;

int n = M.length;

UnionFind uf = new UnionFind(n);

for (int i = 0; i < n - 1; i++) {

for (int j = i + 1; j < n; j++) {

// union friends

if (M[i][j] == 1) {

uf.union(i, j);

}

}

}

return uf.count;

}

}

class UnionFind {

int count;

int[] parent;

int[] rank;

public UnionFind(int n) {

count = n;

parent = new int[n];

rank = new int[n];

for (int i = 0; i < n; i++) {

parent[i] = i;

}

}

public int find(int a) {

return parent[a] == a ? a : find(parent[a]);

}

public void union(int a, int b) {

int rootA = find(a);

int rootB = find(b);

if (rootA == rootB) return;

if (rank[rootA] <= rank[rootB]) {

parent[rootA] = rootB;

rank[rootB] += rank[rootA];

} else {

parent[rootB] = rootA;

rank[rootA] += rank[rootB];

}

count--;

}

public int count() {

return count;

}

}

Last modified 4yr ago