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 numbered 1 through n,
languages[i] is the set of languages the ith user knows, and
friendships[i] = [ui, vi] denotes a friendship between the users ui and vi.
You can choose one language and teach it to some users so that all friends can communicate with each other. Return theminimum 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 3, 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:
class Solution {
Integer[][] memo;
public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
int m = languages.length;
Set<Integer>[] lans = new Set[m];
for (int i = 0; i < languages.length; i ++) {
lans[i] = new HashSet();
for (int l : languages[i]) {
lans[i].add(l);
}
}
int res = m;
memo = new Integer[n + 1][friendships.length + 1];
for (int i = 1; i <= n; i ++) {
res = Math.min(res, dfs(lans, i, friendships, 0));
}
return res;
}
private int dfs(Set<Integer>[] lans, int teach, int[][] friendships, int i) {
if (i == friendships.length) {
return 0;
}
if (memo[teach][i] != null) return memo[teach][i];
int[] friendship = friendships[i];
int a = friendship[0] - 1;
int b = friendship[1] - 1;
Set<Integer> aknows = lans[a];
Set<Integer> bknows = lans[b];
// a b knows nothing in common
int res = lans.length;
if (Collections.disjoint(aknows, bknows)) {
boolean teachA = !aknows.contains(teach);
boolean teachB = !bknows.contains(teach);
int num = 0;
if (teachA) {
aknows.add(teach);
num ++;
}
if (teachB) {
bknows.add(teach);
num ++;
}
res = num + dfs(lans, teach, friendships, i + 1);
if (teachA) aknows.remove(teach);
if (teachB) bknows.remove(teach);
return memo[teach][i] = res;
} else {
return memo[teach][i] = dfs(lans, teach, friendships, i + 1);
}
}
}