You are given the edge list along with their weights. The graph is not necessarily connected and it is undirected. We need to find the summation of edge weight of each connected component of this multigraph.

Using dfs we can identify each of the connected components but as it is a multigraph, I don’t know how to calculate the sum of edge weight.

I think DSU with a “pair<int,int> parent” array so that parent[i].first == root of the component including ith node and parent[i].second == total edge weight upto now might work. We just loop through the edge list and create a connection between two nodes where there exists an edge and add the edge weight to the current parent of this component.

Please enlighten me if DFS can do it for me?