FriendCircles [source code]
public class FriendCircles {
static
/******************************************************************************/
public class Solution {
public int findCircleNum(int[][] M) {
int n = M.length;
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++)
if (!visited[i]) {
count++;
dfs(M, visited, i, n);
}
return count;
}
public void dfs(int[][] M, boolean[] visited, int node, int n) {
if (visited[node])
return;
visited[node] = true;
for (int i = 0; i < n; i++) {
if (i == node)
continue;
if (M[node][i] == 1)
dfs(M, visited, i, n);
}
}
}
/******************************************************************************/
public static void main(String[] args) {
FriendCircles.Solution tester = new FriendCircles.Solution();
int[][][] inputs = {
{//1
{1,1,0},
{1,1,0},
{0,0,1}
},
{//2
{1,0,0,1},
{0,1,1,0},
{0,1,1,1},
{1,0,1,1}
},
};
int[] answers = {
2,//1
1,//2
};
for (int i = 0; i < inputs.length; i++) {
int[][] M = inputs[i];
int ans = answers[i];
System.out.println(Printer.seperator());
int output = tester.findCircleNum(M);
System.out.println(
Printer.wrapColor(Matrix.printMatrix(M), "magenta") +
" -> " + output +
Printer.wrapColor(", expected: " + ans, ans == output ? "green" : "red")
);
}
}
}
这个题的话最直接的做法就是建一个graph, 然后DFS找cycle;
回忆一下基本的DFS的写法的代码的细节, 尤其是main函数跟DFS函数本身之间的关系和对比;
我操这题想复杂了, 这题根本不用找cycle, 直接用一个visited涂色做就行了; 最后的速度是12ms (57%).
无非要注意的地方是:
- DFS代码的细节: 尤其是main函数和DFS函数本身的代码的呼应;
- 没有explicit的graph的题目: 自己首先想好, what is a node, and what is an edge (connection). 多亏了Sedgwick那本书, 这个东西还算有过点锻炼;
刚开始因为找cycle所以给helper的返回值设置的是int. 后来发现只要涂色就行, 所以改成void了. void的DFS是最好写的;
editorial里面除了DFS还给了BFS和UF的解法, 可以学习一下; 不过这个题目DFS最简单是没有争议的了;
DFS解法跟我的基本差不多的; 不过editorial里面提到一个问题, 这个算法的复杂度其实是N^2而不是N! 因为虽然我们只有N个node, 但是每一个node的fanning是N, 所以最后实际上是N^2个call. 也可以这样理解, matrix的每一个entry都被access了;
这个是BFS的解法, editorial2:
public class Solution {
public int findCircleNum(int[][] M) {
int[] visited = new int[M.length];
int count = 0;
Queue < Integer > queue = new LinkedList < > ();
for (int i = 0; i < M.length; i++) {
if (visited[i] == 0) {
queue.add(i);
while (!queue.isEmpty()) {
int s = queue.remove();
visited[s] = 1;
for (int j = 0; j < M.length; j++) {
if (M[s][j] == 1 && visited[j] == 0)
queue.add(j);
}
}
count++;
}
}
return count;
}
}
基本还是差不多的框架, 每一次找到一个unvisited的node, 直接就开始recursion. 只不过这个recursion用BFS来写而已;
这个就是一个trivial translation, 并没有依赖BFS本身peculiar的性质;
另外注意这里的这个BFS其实用于queue本身只有一个循环就行了; 因为这里不需要用到level本身的性质来处理什么东西. 当然你非要加上一个针对level的inner loop, 也可以; discussion里面就有人这么做了;
editorial3是UF的解法, 不过很可惜最后的复杂度居然是N^3, 这个就很尴尬了;
Another method that can be used to determine the number of connected components in a graph is the union find method.
这个是解释初衷; 用来找CC的;
给的文字解释有点姜, 代码看看:
public class Solution {
int find(int parent[], int i) {
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
void union(int parent[], int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
if (xset != yset)
parent[xset] = yset;
}
public int findCircleNum(int[][] M) {
int[] parent = new int[M.length];
Arrays.fill(parent, -1);
for (int i = 0; i < M.length; i++) {
for (int j = 0; j < M.length; j++) {
if (M[i][j] == 1 && i != j) {
union(parent, i, j);
}
}
}
int count = 0;
for (int i = 0; i < parent.length; i++) {
if (parent[i] == -1)
count++;
}
return count;
}
}
again, 看iterative算法的时候不哟啊太纠结于宏观抽象, 而是就从trace入手, 尤其是从第一个iteration就开始跑. 一般都是跑个前三四个iteration才看出来规律的; 不要上来就是ith iteration然后开始inductively思考(i+1)th. 这样有时候是很难具体理解代码的;
注意这种用array表示parent link的方法怎么理解: parent[x] = y大概就跟x.parent = y一样的意思; remind一下箭头是哪个指哪个;
算法本身意思还是很简单的, 通过一个edge-based iteration, 来找到所有有edge的pair, 然后group到一起(设置共同的parent); 这里有一个小的subtltey, 如果x和y不是一个parent, 那么到底谁是新的老大? 也就是谁招安谁? 这里他的这个好像是随意的顺序, 但是实际上不是随意的. 比如说0和3, 那么首先我们i在0, 然后j从0开始走, 走到3, 这个时候0就会被3吞并; 后面当i到3的时候, j到0同时, 那么这个iteration就相当于被跳过了; 所以最后他实际上的吞并顺序是小的数被大的数吞并(大小是index的大小); 既然有一个order的概念存在, 可以理解为这个算法最后是避免了duplicate的;
N^3的复杂度是因为有N^2个pair, 然后每个pair的话有一个find parent的过程, 这个过程是可能有N的;
这个是discussion里面一个高手写的UF:
public class Solution {
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();
}
}
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.
也就是说他这个是一个UF问题的模板解法;
大概看一下, 还是不难理解的. 注意这里他union的写法, 同是对parent和rank两个array怎么更新的; 以及注意一下他这里这个count变量的使用; 这个变量最后计算的就是被成功执行的union操作的数量;
注意他这里如果p和q两个rank相同, 谁增加? 是p增加, 那么p又是什么呢? 实际上就是i, 而他这里iterate的方式(j从i+1开始)保证了最后i是比j小的, 所以最后实际就是index越小的rank越大; 那么有没有想过为什么这样一个count就是我们最后需要的count, 也就是CC的数量呢? 好像基本上就是定义的问题? UF里面的group其实本身就可以跟CC理解为一个差不多的意思? 不对, 本身并没有一个强制的规定, 但是我们这个题目实现的方式就保证了最后每一个group就是一个CC(因为我们使用edge的existence来决定union的: if (edge): we union the two nodes), 所以每一次root不相同导致的union, 就导致发现了两个nodes, which has a connecting edge, but not in the same CC. 然后我们这么一个union, 就减少了一个冗余的CC. 最后实际上剩下来的group数量也就是CC数量就是我们要的数量;
这里他find的过程用的是iteration而不是recursion, 看起来稍微显得有点复杂一点;
另外注意他这里的path compression的实现方法: 最好自己还是画图看一下, 这个做法并不是那么trivial; 在画图的时候, 大root记得画一个self-cycle, 这个是题目设置的意思, 而且还正好是这里循环的header; 这个做法具体还是不太好解释, 大概画画图才能看出来, 最后每一次这个循环, 当前path的长度减少一半; 从p开始, parent改成当前parent的parent, 也就是跳过了当前的旧parent, 然后自己再跳到新的parent, 让这个新parent也完成一个跳子. 最后总的path长度就减半了; 还是有点意思的;
这个是一个很粗糙的UF解法:
public int findCircleNum(int[][] M) {
int m = M.length, cnt = 0;
int[] root = new int[m];
for (int i = 0; i < m; i++) root[i] = i;
for (int i = 0; i < m; i++)
for (int j = i + 1; j < m; j++)
if (M[i][j] == 1) unionFind(root, i, j);
for (int i = 0; i < m; i++)
if (i == root[i]) cnt++;
return cnt;
}
void unionFind (int[] root, int v1, int v2) {
while (root[v1] != v1) v1 = root[v1]; //find v1's root
while (root[v2] != v2) v2 = root[v2]; //find v2's root
if (root[v1] != root[v2]) root[v2] = v1; //unite the 2 subtrees
}
这个其实原理也是一样的, 不过写法就简单了很多;
I do not think it is necessary to count the root nodes after the union-find operations, you just need minus 1 when you do a union operation.
这个就是应用了之前模板解法上面的一个技巧;
以及这个人的版本:
public int findCircleNum(int[][] M) {
int count = M.length, roots[] = IntStream.range(0, M.length).toArray();
for (int i = 0; i < M.length; i++)
for (int j = i + 1, rootI = getRoot(roots, i), rootJ; j < M.length; j++)
if (M[i][j] == 1 && rootI != (rootJ = getRoot(roots, j))) {
roots[rootJ] = rootI;
count--;
}
return count;
}
public int getRoot(int[] roots, int leaf) {
while (leaf != roots[leaf]) leaf = roots[leaf] = roots[roots[leaf]];
return leaf;
}
这个跟上面那个path compression好像是一样的, 连着的等号好像是从右到左的; 也就是left assoc的.
另外, 关于rank:
Hi I think I found the answer from the book "Introduction to Algorithms" "CLRS". Basically this will provide a clue when you try to union 2 sets. 1 shorter 1 longer and bigger. So when you union, you would just want to update as few as possible. So we can keep a rank record to help us decide who is the smaller one and who is the bigger one to save us some time.
所以rank只不过是一个加速的技巧. 如果你没有, 也不是不可以;
发现这个人的模板就是直接从Sedgwick那里改过来的;
discussion基本就没有什么其他的解法了;
Problem Description
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.
Difficulty:Medium
Total Accepted:12.2K
Total Submissions:24.5K
Contributor: lkpunisher
Companies
two sigma
Related Topics
depth-first search union find
Similar Questions
Number of Connected Components in an Undirected Graph