On a social network consisting of m
users and some friendships between users, two users can communicate with each other if they know a common language.
You are given an integer n
, an array languages
, and an array friendships
where:
- There are
n
languages numbered1
throughn
, languages[i]
is the set of languages theith
user knows, andfriendships[i] = [ui, vi]
denotes a friendship between the usersui
andvi
.
You can choose one language and teach it to some users so that all friends can communicate with each other. Return the minimum number of users you need to teach.Note that friendships are not transitive, meaning if x
is a friend of y
and y
is a friend of z
, this doesn’t guarantee that x
is a friend of z
.
Example 1:
Input: n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]] Output: 1 Explanation: You can either teach user 1 the second language or user 2 the first language.
Example 2:
Input: n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]] Output: 2 Explanation: Teach the third language to users 1 and 2, yielding two users to teach.
Constraints:
2 <= n <= 500
languages.length == m
1 <= m <= 500
1 <= languages[i].length <= n
1 <= languages[i][j] <= n
1 <= ui < vi <= languages.length
1 <= friendships.length <= 500
- All tuples
(ui, vi)
are unique languages[i]
contains only unique values
Solution: Brute Force
Enumerate all languages and see which one is the best.
If two friends speak a common language, we can skip counting them.
Time complexity: O(m*(n+|friendship|))
Space complexity: O(m*n)
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 |
// Author: Huahua class Solution { public: int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) { const int m = languages.size(); vector<unordered_set<int>> langs; for (auto& l : languages) { sort(begin(l), end(l)); langs.emplace_back(begin(l), end(l)); } for (auto& e : friendships) { const auto& l0 = languages[--e[0]]; const auto& l1 = languages[--e[1]]; vector<int> common; set_intersection(begin(l0), end(l0), begin(l1), end(l1), back_inserter(common)); if (common.size()) e[0] = e[1] = -1; } int ans = INT_MAX; for (int i = 1; i <= n; ++i) { vector<int> users(m); for (const auto& e : friendships) { // e[0] and e[1] have a common language, skip this edge if (e[0] == -1) continue; if (!langs[e[0]].count(i)) users[e[0]] = 1; if (!langs[e[1]].count(i)) users[e[1]] = 1; } ans = min(ans, accumulate(begin(users), end(users), 0)); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment