{"id":8008,"date":"2021-01-23T13:26:49","date_gmt":"2021-01-23T21:26:49","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8008"},"modified":"2021-01-23T13:27:04","modified_gmt":"2021-01-23T21:27:04","slug":"leetcode-1733-minimum-number-of-people-to-teach","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1733-minimum-number-of-people-to-teach\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1733. Minimum Number of People to Teach"},"content":{"rendered":"\n<p>On a social network consisting of&nbsp;<code>m<\/code>&nbsp;users and some friendships between users, two users can communicate with each other if they know a common language.<\/p>\n\n\n\n<p>You are given an integer&nbsp;<code>n<\/code>, an array&nbsp;<code>languages<\/code>, and an array&nbsp;<code>friendships<\/code>&nbsp;where:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>There are&nbsp;<code>n<\/code>&nbsp;languages numbered&nbsp;<code>1<\/code>&nbsp;through&nbsp;<code>n<\/code>,<\/li><li><code>languages[i]<\/code>&nbsp;is the set of languages the&nbsp;<code>i<sup>\u200b\u200b\u200b\u200b\u200b\u200bth<\/sup><\/code>\u200b\u200b\u200b\u200b user knows, and<\/li><li><code>friendships[i] = [u<sub>\u200b\u200b\u200b\u200b\u200b\u200bi<\/sub>\u200b\u200b\u200b, v<sub>\u200b\u200b\u200b\u200b\u200b\u200bi<\/sub>]<\/code>&nbsp;denotes a friendship between the users&nbsp;<code>u<sup>\u200b\u200b\u200b\u200b\u200b<\/sup><sub>\u200b\u200b\u200b\u200b\u200b\u200bi<\/sub><\/code>\u200b\u200b\u200b\u200b\u200b and&nbsp;<code>v<sub>i<\/sub><\/code>.<\/li><\/ul>\n\n\n\n<p>You can choose&nbsp;<strong>one<\/strong>&nbsp;language and teach it to some users so that all friends can communicate with each other. Return&nbsp;<em>the<\/em>&nbsp;<em><strong>minimum<\/strong>&nbsp;<\/em><em>number of users you need to teach.<\/em>Note that friendships are not transitive, meaning if&nbsp;<code>x<\/code>&nbsp;is a friend of&nbsp;<code>y<\/code>&nbsp;and&nbsp;<code>y<\/code>&nbsp;is a friend of&nbsp;<code>z<\/code>, this doesn&#8217;t guarantee that&nbsp;<code>x<\/code>&nbsp;is a friend of&nbsp;<code>z<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> You can either teach user 1 the second language or user 2 the first language.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> Teach the third language to users 1 and 2, yielding two users to teach.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= n &lt;= 500<\/code><\/li><li><code>languages.length == m<\/code><\/li><li><code>1 &lt;= m &lt;= 500<\/code><\/li><li><code>1 &lt;= languages[i].length &lt;= n<\/code><\/li><li><code>1 &lt;= languages[i][j] &lt;= n<\/code><\/li><li><code>1 &lt;= u<sub>\u200b\u200b\u200b\u200b\u200b\u200bi<\/sub>&nbsp;&lt; v<sub>\u200b\u200b\u200b\u200b\u200b\u200bi<\/sub>&nbsp;&lt;= languages.length<\/code><\/li><li><code>1 &lt;= friendships.length &lt;= 500<\/code><\/li><li>All tuples&nbsp;<code>(u<sub>\u200b\u200b\u200b\u200b\u200bi,&nbsp;<\/sub>v<sub>\u200b\u200b\u200b\u200b\u200b\u200bi<\/sub>)<\/code>&nbsp;are unique<\/li><li><code>languages[i]<\/code>&nbsp;contains only unique values<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Brute Force<\/strong><\/h2>\n\n\n\n<p>Enumerate all languages and see which one is the best.<\/p>\n\n\n\n<p>If two friends speak a common language, we can skip counting them.<\/p>\n\n\n\n<p>Time complexity: O(m*(n+|friendship|))<br>Space complexity: O(m*n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {\n    const int m = languages.size();\n    vector<unordered_set<int>> langs;\n    for (auto& l : languages) {\n      sort(begin(l), end(l));\n      langs.emplace_back(begin(l), end(l));\n    }\n    for (auto& e : friendships) {\n      const auto& l0 = languages[--e[0]];\n      const auto& l1 = languages[--e[1]];\n      vector<int> common;\n      set_intersection(begin(l0), end(l0), begin(l1), end(l1), back_inserter(common));\n      if (common.size()) e[0] = e[1] = -1;\n    }\n    int ans = INT_MAX;\n    for (int i = 1; i <= n; ++i) {\n      vector<int> users(m);\n      for (const auto& e : friendships) {\n         \/\/ e[0] and e[1] have a common language, skip this edge\n        if (e[0] == -1) continue;\n        if (!langs[e[0]].count(i)) users[e[0]] = 1;\n        if (!langs[e[1]].count(i)) users[e[1]] = 1;\n      }\n      ans = min(ans, accumulate(begin(users), end(users), 0));      \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>On a social network consisting of&nbsp;m&nbsp;users and some friendships between users, two users can communicate with each other if they know a common language. You&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[77,177],"class_list":["post-8008","post","type-post","status-publish","format-standard","hentry","category-graph","tag-graph","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8008","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8008"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8008\/revisions"}],"predecessor-version":[{"id":8010,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8008\/revisions\/8010"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8008"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8008"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8008"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}