Problem:
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 ithand 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:
|
1 2 3 4 5 |
Input: [[1,1,0], [1,1,0], [0,0,1]] Output: 2 |
Example 2:
|
1 2 3 4 5 |
Input: [[1,1,0], [1,1,1], [0,1,1]] Output: 1 |
- N is in range [1,200].
- M[i][i] = 1 for all students.
- If M[i][j] = 1, then M[j][i] = 1.
Idea:
Find all connected components using DFS
Solution: DFS
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua // Time complexity: O(n^2) // Space complexity: O(n) // Running Time: 25 ms class Solution { public: int findCircleNum(vector<vector<int>>& M) { if (M.empty()) return 0; int n = M.size(); int ans = 0; for (int i = 0; i < n; ++i) { if (!M[i][i]) continue; ++ans; dfs(M, i, n); } return ans; } private: void dfs(vector<vector<int>>& M, int curr, int n) { // Visit all friends (neighbors) for (int i = 0; i < n; ++i) { if (!M[curr][i]) continue; M[curr][i] = M[i][curr] = 0; dfs(M, i, n); } } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua // Time complexity: O(n^2) // Space complexity: O(n) // Running Time: 20 ms class Solution { public int findCircleNum(int[][] M) { int n = M.length; if (n == 0) return 0; int ans = 0; for (int i = 0; i < n; ++i) { if (M[i][i] == 0) continue; ++ans; dfs(M, i, n); } return ans; } private void dfs(int[][] M, int curr, int n) { for (int i = 0; i < n; ++i) { if (M[curr][i] == 0) continue; M[curr][i] = M[i][curr] = 0; dfs(M, i, n); } } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
""" Author: Huahua Time complexity: O(n^2) Space complexity: O(n) Running Time: 162 ms """ class Solution(object): def findCircleNum(self, M): """ :type M: List[List[int]] :rtype: int """ def dfs(M, curr, n): for i in xrange(n): if M[curr][i] == 1: M[curr][i] = M[i][curr] = 0 dfs(M, i, n) n = len(M) ans = 0 for i in xrange(n): if M[i][i] == 1: ans += 1 dfs(M, i, n) return ans |
Solution 2: Union Find
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
// Author: Huahua // Runtime: 19 ms class UnionFindSet { public: UnionFindSet(int n) { parents_ = vector<int>(n + 1, 0); ranks_ = vector<int>(n + 1, 0); for (int i = 0; i < parents_.size(); ++i) parents_[i] = i; } bool Union(int u, int v) { int pu = Find(u); int pv = Find(v); if (pu == pv) return false; if (ranks_[pu] > ranks_[pv]) { parents_[pv] = pu; } else if (ranks_[pv] > ranks_[pu]) { parents_[pu] = pv; } else { parents_[pu] = pv; ++ranks_[pv]; } return true; } int Find(int id) { if (id != parents_[id]) parents_[id] = Find(parents_[id]); return parents_[id]; } private: vector<int> parents_; vector<int> ranks_; }; class Solution { public: int findCircleNum(vector<vector<int>>& M) { int n = M.size(); UnionFindSet s(n); for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (M[i][j] == 1) s.Union(i, j); unordered_set<int> circles; for (int i = 0; i < n; ++i) circles.insert(s.Find(i)); return circles.size(); } }; |
