题目描述
在一个由 m
个用户组成的社交网络里,我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。
给定一个整数 n
,数组 languages
和数组 friendships
,它们的含义如下:
- 总共有
n
种语言,编号从1
到n
。 languages[i]
是第i
位用户掌握的语言集合。friendships[i] = [u_i, v_i]
表示u_i
和v_i
为好友关系。
你可以选择 一门 语言并教会一些用户,使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。
请注意,好友关系没有传递性,也就是说如果 x
和 y
是好友,且 y
和 z
是好友,x
和 z
不一定是好友。
样例
输入:n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
输出:1
解释:你可以选择教用户 1 第二门语言,也可以选择教用户 2 第一门语言。
输入:n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
输出:2
解释:教用户 1 和用户 3 第三门语言,需要教 2 名用户。
限制
2 <= n <= 500
languages.length == m
1 <= m <= 500
1 <= languages[i].length <= n
1 <= languages[i][j] <= n
1 <= u_i < v_i <= languages.length
1 <= friendships.length <= 500
- 所有的好友关系
(u_i, v_i)
都是唯一的。 languages[i]
中包含的值互不相同。
算法
(暴力枚举,哈希表) $O(nm)$
- 初始化每个人会的语言的哈希表,并过滤出不能沟通的好友关系。
- 枚举教哪一门语言,根据不能沟通的好友关系,统计需要培训的人,更新最小值。
时间复杂度
- 初始化需要 $O(nm)$ 的时间,枚举答案需要 $O(nm)$ 的时间,故总时间复杂度为 $O(nm)$。
空间复杂度
- 需要 $O(nm)$ 的空间存储每个人会的语言的哈希表,和不能沟通的好友关系。
C++ 代码
class Solution {
public:
int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
const int m = languages.size();
vector<vector<bool>> lang(m, vector<bool>(n, false));
for (int i = 0; i < m; i++)
for (int l : languages[i])
lang[i][l - 1] = true;
vector<vector<int>> f;
for (const auto &e : friendships) {
int x = e[0] - 1, y = e[1] - 1;
bool ok = false;
for (int i = 0; i < n; i++)
if (lang[x][i] && lang[y][i]) {
ok = true;
break;
}
if (!ok)
f.push_back(e);
}
int ans = m;
for (int i = 0; i < n; i++) {
vector<bool> need(m, false);
for (const auto &e : f) {
int x = e[0] - 1, y = e[1] - 1;
need[x] = need[y] = true;
}
int tot = 0;
for (int j = 0; j < m; j++)
if (need[j] && !lang[j][i])
tot++;
if (tot < ans)
ans = tot;
}
return ans;
}
};