最小生成树

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
/*
 链接：https://www.nowcoder.com/questionTerminal/c23eab7bb39748b6b224a8a3afbe396b
来源：牛客网

一个有n户人家的村庄，有m条路连接着。村里现在要修路，每条路都有一个代价，
现在请你帮忙计算下，最少需要花费多少的代价，就能让这n户人家连接起来。

输入描述:
输入第一行，两个整数n,m;
接下来m行，每行三个整数a,b,c，表示有路连接编号为a和b的人家，修路要花费的代价为c。
数据保证能将每户人家都连接起来。
注意重边的情况。

输出描述:
输出最小的花费代价使得这n户人家连接起来。
示例1
输入
3 3
1 3 3
1 2 1
2 3 1
输出
2
K算法
 */
namespace 最小生成树 {
public class Node {
    public int val;
    public List<Node> neighbors;
    public List<Edge> nextEdges;
    public Node(int val) {
        this.val = val;
        neighbors = new List<Node>();
        nextEdges = new List<Edge>();
    }
}
public class Edge {
    public int weight;
    public Node to;
    public Node from;
    public Edge(int weight, Node to, Node from) {
        this.weight = weight;
        this.to = to;
        this.from = from;
    }
}
public class Graph {
    public Dictionary<int, Node> nodeDic;
    public HashSet<Edge> edges;
    public Graph() {
        nodeDic = new Dictionary<int, Node>();
        edges = new HashSet<Edge>();
    }
}
public class Program {
    public class smallEdge : IComparer<Edge> {
        public int Compare(Edge x, Edge y) {
            return x.weight - y.weight;
        }
    }
    public static void Main() {
        string line = Console.ReadLine();
        string[] tokens = line.Split();
        int N = int.Parse(tokens[0]);
        int M = int.Parse(tokens[1]);

        Graph graph = new Graph();
        GreatHeap<Edge> small = new GreatHeap<Edge>(new smallEdge());
        List<Node> nodes = new List<Node>();
        for (int i = 0; i < M; i++) {
            tokens = Console.ReadLine().Split();
            int p1 = int.Parse(tokens[0]);
            int p2 = int.Parse(tokens[1]);
            int p3 = int.Parse(tokens[2]);

            Node node1 = null, node2 = null;
            if (graph.nodeDic.ContainsKey(p1)) {
                node1 = graph.nodeDic[p1];
            } else {
                node1 = new Node(p1);
                nodes.Add(node1);
                graph.nodeDic.Add(p1, node1);
            }
            if (graph.nodeDic.ContainsKey(p2)) {
                node2 = graph.nodeDic[p2];
            } else {
                node2 = new Node(p2);
                nodes.Add(node2);
                graph.nodeDic.Add(p2, node2);
            }
            Edge edge = new Edge(p3, node1, node2);

            small.Push(edge);
            graph.edges.Add(edge);
        }
        UnionSet us = new UnionSet(nodes);
        int ans = 0;
        while (small.Count != 0) {
            Edge cur = small.Pop();
            if (!us.IsSameSet(cur.to, cur.from)) {
                us.Union(cur.to, cur.from);
                ans += cur.weight;
            }
        }
        Console.WriteLine(ans);
    }

    public class UnionSet {
        private Node[] father;
        private int[] size;
        private Node[] help;
        public UnionSet(List<Node> nodes) {
            father = new Node[100001];
            size = new int[100001];
            help = new Node[100001];
            foreach (var item in nodes) {
                father[item.val] = item;
                size[item.val] = 1;
            }
        }
        private Node FindFather(Node value) {
            Node cur = value;
            int helpIndex = 0;
            while (cur != father[cur.val]) {
                help[helpIndex++] = cur;
                cur = father[cur.val];
            }
            for (int i = 0; i < helpIndex; i++) {
                father[help[i].val] = cur;
            }
            return cur;
        }
        public void Union(Node a, Node b) {
            Node af = FindFather(a);
            Node bf = FindFather(b);
            if (af != bf) {
                int asize = size[af.val];
                int bsize = size[bf.val];
                Node small = asize < bsize ? af : bf;
                Node big = small == af ? bf : af;
                size[big.val] += size[small.val];
                father[small.val] = father[big.val];
            }
        }
        public bool IsSameSet(Node a, Node b) {
            return FindFather(a) == FindFather(b);
        }
    }
    public class GreatHeap<T> where T : class {
        private List<T> heap;
        private Dictionary<T, int> indexDic;
        private int heapSize;
        public IComparer<T> comp;
        public GreatHeap(IComparer<T> comp) {
            this.comp = comp;
            heapSize = 0;
            heap = new List<T>();
            indexDic = new Dictionary<T, int>();
        }
        public int Count => heapSize;

        public void Push(T obj) {
            heap.Add(obj);
            indexDic.Add(obj, heapSize);
            HeapInsert(heapSize++);
        }
        public T Pop() {
            T ans = heap[0];
            Swap(0, --heapSize);
            Heapify(0);
            heap.RemoveAt(heapSize);
            indexDic.Remove(ans);
            return ans;
        }

        private void Heapify(int index) {
            int left = index * 2 + 1;
            while (left < heapSize) {
                int best = left + 1 < heapSize &&
                           comp.Compare(heap[left + 1], heap[left]) < 0 ? left + 1 : left;
                best = comp.Compare(heap[best], heap[index]) < 0 ? best : index;
                if (index == best) {
                    break;
                }
                Swap(index, best);
                index = best;
                left = index * 2 + 1;
            }
        }
        private void HeapInsert(int index) {
            while (comp.Compare(heap[index], heap[(index - 1) / 2]) < 0) {
                Swap(index, (index - 1) / 2);
                index = (index - 1 ) / 2;
            }
        }
        private void Swap(int i, int j) {
            T objI = heap[i];
            T objJ = heap[j];

            indexDic[objI] = j;
            indexDic[objJ] = i;

            heap[i] = objJ;
            heap[j] = objI;
        }
    }
}
}