LeetCode 547 - Friend Circles

https://leetcode.com/problems/friend-circles

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 directfriends 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:

1. N is in range [1,200].
2. M[i][i] = 1 for all students.
3. If M[i][j] = 1, then M[j][i] = 1.

https://discuss.leetcode.com/topic/85039/java-solution-union-find

This is a typical Union Find problem. I abstracted it as a standalone class. Remember the template, you will be able to use it later.

    class UnionFind {
        private int count = 0;
        private int[] parent, 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 p) {
         while (p != parent[p]) {
                parent[p] = parent[parent[p]];    // path compression by halving
                p = parent[p];
            }
            return p;
        }
        
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;
            if (rank[rootQ] > rank[rootP]) {
                parent[rootP] = rootQ;
            }
            else {
                parent[rootQ] = rootP;
                if (rank[rootP] == rank[rootQ]) {
                    rank[rootP]++;
                }
            }
            count--;
        }
        
        public int count() {
            return count;
        }
    }
    
    public int findCircleNum(int[][] M) {
        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++) {
                if (M[i][j] == 1) uf.union(i, j);
            }
        }
        return uf.count();
    }

https://www.nowtoshare.com/zh/Article/Index/70560
public int findCircleNum(int[][] M) { int size=M.length; if(size==0) return 0; UnionFind uf = new UnionFind(size); for(int i=0; i<size;i++){ for(int j=0; j<size; j++){ if(i==j) continue; if(M[i][j]==1){ uf.union(i,j); } } } return uf.cycles(); } public class UnionFind{ public int[] arr; public UnionFind(int size){ arr = new int[size]; for(int i=0;i<size; i++){ arr[i]=i; } } public int root(int i){ while(arr[i] !=i){ arr[i] =arr[arr[i]]; i=arr[i]; } return i; } public void union(int i, int j){ int r1 =root(i); int r2 =root(j); if(r1 == r2) return; arr[r1] =r2; } public int cycles(){ int cnt=0; for(int i=0;i<arr.length ;i++){ if(arr[i] == i){ cnt++; } } return cnt; } }

X. DFS
https://discuss.leetcode.com/topic/85031/neat-dfs-java-solution

BTW, visited use boolean[] better.

    public void dfs(int[][] M, int[] visited, int i) {
        for (int j = 0; j < M.length; j++) {
            if (M[i][j] == 1 && visited[j] == 0) {
                visited[j] = 1;
                dfs(M, visited, j);
            }
        }
    }
    public int findCircleNum(int[][] M) {
        int[] visited = new int[M.length];
        int count = 0;
        for (int i = 0; i < M.length; i++) {
            if (visited[i] == 0) {
                dfs(M, visited, i);
                count++;
            }
        }
        return count;
    }

X. BFS
https://discuss.leetcode.com/topic/85021/java-bfs-equivalent-to-finding-connected-components-in-a-graph

public int findCircleNum(int[][] M) {
    int count = 0;
    for (int i=0; i<M.length; i++)
        if (M[i][i] == 1) { count++; BFS(i, M); }
    return count;
}

public void BFS(int student, int[][] M) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(student);
    while (queue.size() > 0) {
        int queueSize = queue.size();
        for (int i=0;i<queueSize;i++) {
            int j = queue.poll();
            M[j][j] = 2; // marks as visited
            for (int k=0;k<M[0].length;k++) 
                if (M[j][k] == 1 && M[k][k] == 1) queue.add(k);
        }
    }
}

http://bookshadow.com/weblog/2017/04/03/leetcode-friend-circles/

Floyd-Warshall 求传递闭包

Floyd-Warshall算法参阅：

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

def findCircleNum(self, M): """ :type M: List[List[int]] :rtype: int """ N = len(M) for k in range(N): for i in range(N): for j in range(N): M[i][j] = M[i][j] or (M[i][k] and M[k][j]) cnt = 0 vset = set() for x in range(N): if x not in vset: cnt += 1 for y in range(x + 1, N): if M[x][y]: vset.add(y) return cnt

http://www.ideserve.co.in/learn/friend-circles-graph
There are n students in a class. Every student can have 0 or more friends. If A is a friend of B and B is a friend of C then A and C are also friends. So we define a friend circle as a group of students who are friends as given by above definition. Given an nXn-matrix friends which consists of characters Y or N. If friends[i][j]=Y, then ith and jth students are friends, friends[i][j]=N, then i and j are not friends. Find the total number of such friend circles in the class.
DFS:

9	public static int getFriendCircles(char[][] friends) {
10
11	if (friends == null || friends.length < 1)
12	return 0;
13
14	int noOfCircles = 0;
15
16	boolean visited[] = new boolean[friends.length];
17
18	for (int i = 0; i < visited.length; i++)
19	visited[i] = false;
20
21	for (int i = 0; i < friends.length; i++) {
22	if (!visited[i]) {
23	noOfCircles++;
24	visited[i] = true;
25	findFriends(friends, visited, i);
26	}
27	}
28
29	return noOfCircles;
30
31	}
32
33	public static void findFriends(char[][] friends, boolean[] visited, int id) {
34
35	for (int i = 0; i < friends.length; i++) {
36	if (!visited[i] && i != id && 'Y' == friends[id][i]) {
37	visited[i] = true;
38	findFriends(friends, visited, i);
39	}
40	}
41
42	}