leetcode_day57

今日内容：

• 寻找存在的路径
• 721. 账户合并 medium

寻找存在的路径

题目：

给定一个包含 n 个节点的无向图中，节点编号从 1 到 n （含 1 和 n ）。

你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。

输入描述

第一行包含两个正整数 N 和 M，N 代表节点的个数，M 代表边的个数。

后续 M 行，每行两个正整数 s 和 t，代表从节点 s 与节点 t 之间有一条边。

最后一行包含两个正整数，代表起始节点 source 和目标节点 destination。

输出描述

输出一个整数，代表是否存在从节点 source 到节点 destination 的路径。如果存在，输出 1；否则，输出 0。

思路：

并查集模板题，只需要建一个并查集，然后判断source和destination是不是同源。

代码

#include <bits/stdc++.h>

using namespace std;

class Union{//并查集
public:
    vector<int> f;
    Union(int n) {
        f.resize(n);
        for(int i = 0;i < n;i++) {
            f[i] = i;
        }
    }
    int find(int u) {
        if(f[u] != u) {
            return f[u] = find(f[u]);
        }
        return f[u];
    }
    void join(int u, int v) {
        f[find(u)] = find(v);
    }
    bool isSame(int u, int v) {
        return find(u) == find(v);
    }
};

int main () {
    int N, M;
    cin >> N >> M;
    Union uf(N + 1);
    for(int i = 0;i < M;i++) {//建立并查集
        int a, b;
        cin >> a >> b;
        uf.join(a, b);
    }
    int s, d;
    cin >> s >> d;
    cout << uf.isSame(s, d);//判断
    return 0;
}

721. 账户合并

题目：

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。

现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。

示例 1：

输入：accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
输出：[["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
解释：
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "johnsmith@mail.com"。 
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正确的。

思路：

由于今天并查集专题开始，只有一道模板题，所以将前天的力扣每日一题记录，正好也是并查集，提前学过就是快。

• 给所有的邮箱名编号，方便加入并查集，同时将邮件和名字关联，建立map<email, name>
• 根据每个账户的邮箱的编号，为每个账户建立并查集，以每个账户的第一个邮箱作为root
• 遍历所有的邮箱，建立"邮箱->编号"的映射，实现：能够根据一个邮箱得到邮箱所有者的全部邮箱
  • 得到该邮箱的root编号，建立map<index, emails>，将该邮箱放入root编号对应的邮箱集中
• 遍历所有邮箱集，此时邮箱集已经完成合并，排序，通过第一步的邮箱->名字映射得到姓名，合并成一个数组加入答案，并返回。

详见代码注释，可学习其中对于map的遍历简洁写法:auto [e,_] : map

代码

class UnionFind {
public:
    vector<int> parent;

    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    void join(int index1, int index2) {
        parent[find(index1)] = find(index2);
    }

    int find(int index) {
        if (parent[index] != index) {
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        //原来是并查集，没学过，现在学了
        //首先给邮件编号方便加入并查集
        map<string, int> emailToIndex;
        //把邮件和名字关联起来
        map<string, string> emailToName;
        int emailIndex = 0;
        for(auto& account : accounts) {
            string & name = account[0];
            int size = account.size();
            for(int i = 1;i < size;i++) {
                string & email = account[i];
                if(!emailToIndex.count(email)) {
                    emailToIndex[email] = emailIndex++;
                    emailToName[email] = name;
                }
            }
        }
        //构建并查集
        UnionFind uf(emailIndex);
        for(auto & account : accounts) {
            string & first = account[1];//第一个email作根
            int root = emailToIndex[first];
            int size = account.size();
            for(int i = 2;i < size;i++) {
                string & email = account[i];
                int index = emailToIndex[email];
                uf.join(index, root);
            }
        }
        //将同一个人的emails统一起来
        map<int, vector<string>> indexToEmails;
        for(auto & [email, _] : emailToIndex) {
            int index = uf.find(emailToIndex[email]);//得到该email的根
            vector<string>& emails = indexToEmails[index];//得到这个根下已经有的emails
            emails.emplace_back(email);//将当前email加入这个根下的emails
            indexToEmails[index] = emails;//放回去
        }
        vector<vector<string>> ans;
        for(auto & [_, emails] : indexToEmails) {
            sort(emails.begin(), emails.end());//按ASCII排序
            string & name = emailToName[emails[0]];
            vector<string> account;
            account.emplace_back(name);//名字打头
            for(auto & email : emails) {
                account.emplace_back(email);//后跟email
            }
            ans.emplace_back(account);
        }
        return ans;
    }
};