力扣2492：并查集/dfs

方法一：并查集。如果不仔细读题，可能会想着把每一个一维数组下标为2的位置进行排序即可。但这是不行的。因为有可能有一些节点在其它集合当中。如果这些节点之间存在一个边权值比节点1所在集合的最小边权值还要小，那么求出来的答案就是错的。

由于城市1与城市n之间至少有一条路径，那么也就意味着城市1与城市n是在同一个集合中。我们只需要求出这个集合中的边权值的最小值即可。

class Solution
{
public:
    int find(vector<int>& father, int u)
    {
        return u == father[u] ? u : father[u] = find(father, father[u]);
    }
    void join(vector<int>& father, int u, int v)
    {
        u = find(father, u);
        v = find(father, v);
        if (u == v) return;
        father[v] = u;
    }
    int minScore(int n, vector<vector<int>>& roads)
    {
        vector<int>father(n + 1);
        for (int i = 1; i <= n; i++)
        {
            father[i] = i;
        }
        for (auto p : roads)
        {
            join(father, p[0], p[1]);
        }
        unordered_map<int, int>mp;//mp.first:根节点编号  mp.second:该集合的边权最小值
        for (auto p : roads)
        {
            mp[find(father, p[0])] = INT_MAX;
        }
        for (auto p : roads)
        {
            if (find(father, n) == find(father, p[0]))
            {
                if (p[2] < mp[find(father, p[0])])
                {
                    mp[find(father, p[0])] = p[2];
                }
            }
        }
        return mp[find(father, n)];
    }
};

并查集的模板，见：并查集（力扣1971）-CSDN博客

方法二：深度优先搜索

由于题目说了确保节点1与节点n之间存在至少一条路径，因此只需要对节点1所在的集合进行深度优先搜索即可。在深度优先搜索的过程中维护边权最小值。

在深搜之前，我们需要构建一个邻接矩阵进行节点的存储。

class Solution
{
public:
    unordered_map<int, vector<pair<int, int>>>graph;//第一个int，表示起点，第二个int表示终点，第三个int表示边权值
    int ans = INT_MAX;
    vector<bool>vis;
    void dfs(int x)
    {
        vis[x] = true;
        for (auto it : graph[x])
        {
            ans = min(ans, it.second);
            if (!vis[it.first]) dfs(it.first);
        }
    }
    int minScore(int n, vector<vector<int>>& roads)
    {
        for (auto p : roads)
        {
            graph[p[0]].push_back({ p[1],p[2] });
            graph[p[1]].push_back({ p[0],p[2] });
        }
        vis = vector<bool>(n + 1, false);
        dfs(1);
        return ans;
    }
};