Kruskal算法

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <set>
#include "disjoint-set.hpp"
#include <string>
#include <queue>
using namespace std;

void read_graph(string input_file, unordered_map<int, vector<pair<int, int>>>& adj_list)
{
    FILE* fptr = fopen(input_file.c_str(), "r");
    int node_cnt;
    fscanf_s(fptr, "%d", &node_cnt);
    for (int i = 0; i < node_cnt; i++)
    {
        int node;
        fscanf_s(fptr, "%d", &node);
        vector<pair<int, int>> empty;
        adj_list[node] = empty;
    }

    int edge_cnt;
    fscanf_s(fptr, "%d", &edge_cnt);
    for (int i = 0; i < edge_cnt; i++)
    {
        int start;
        int end;
        int weight;
        fscanf_s(fptr, "%d%d%d", &start, &end, &weight);
        adj_list[start].push_back({ end, weight });
    }
}

int main()
{
    unordered_map<int, vector<pair<int, int>>> adj_list;
    read_graph("input.txt", adj_list);

    DisjointSet d;
    vector<vector<int>> q;
    
    for (auto& entry : adj_list)
    {
        int a = entry.first;
        d.insert(a);
        for (auto& p : entry.second)
        {
            int b = p.first;
            int w = p.second;
            d.insert(b);
            q.push_back({ a, b, w });
        }
    }

    sort(q.begin(), q.end(), [](vector<int> v1, vector<int> v2)
        {
            int w1 = v1[v1.size() - 1];
            int w2 = v2[v2.size() - 1];
            return w1 < w2 ? 1 : 0;
        });

    vector<vector<int>> ans;
    for (vector<int>& line : q)
    {
        int a = line[0];
        int b = line[1];
        if (!d.isConnected(a, b))
        {
            d.join(a, b);
            ans.push_back(line);
            if (ans.size() == adj_list.size() - 1)
            {
                break;
            }
        }
    }

    return 0;
}

7
1
2
3
4
5
6
7
12
1   2   2 
1   4   1
2   4   3
2   5   10
3   1   4
3   6   5
4   3   2
4   6   8
4   7   4
4   5   7
5   7   6
7   6   1