I'm trying to solve a competitive programming problem. It basically gives a undirected graph (tree-like: no multiple paths between two nodes...) and asks for the sum of all possible paths between any pair of nodes in the graph (each path must be counted only once, in other words, if you have already counted the path from A to B, you shouldn't count the path from B to A).
To solve this, I've tried to remove each edge (separating the tree in 2 components) and count the number of vertices in one of the components (the count of nodes of the second component can be derived from the count found in the first).
The total weight that a edge will contribute is: (the number of paths that pass by it = first_component_size * second_component_size) * (the weight of the edge).
Input description:
The input is composed of several instances (the number of instances is given on the first line of input).
The first input row of each instance contains an integer N (1 ≤ N ≤ 10000), representing the number of nodes. The nodes are enumerated from 1 to N.
Each one of the following N-1 rows contains three integers A, B and C (1 ≤ A, B ≤ N, 1 ≤ C ≤ 50), indicating that the edge that connects the nodes A and B has length C.
Output description:
For each instance print the sum of lenghts of the paths that connects all the pairs of nodes. The answer must be in MOD 1300031.
#include <cstdio>
#include <vector>
#include <utility>
const int MOD = 1300031;
using edge = std::pair<int, int>;
using adj_list = std::vector<edge>;
using graph = std::vector<adj_list> ;
struct myEdge {
int from, to, weight;
};
std::vector<bool> visited;
int count_nodes_on_component(graph &g, int v) {
int count_of_nodes = 1; //1 for itself
adj_list &adj = g[v];
for(auto &e : adj) {
if(!visited[e.first]) {
visited[e.first] = true;
count_of_nodes += count_nodes_on_component(g, e.first);
visited[e.first] = false;
}
}
return count_of_nodes;
}
int main ( void ) {
int test_cases;
scanf("%d", &test_cases);
while (test_cases--) {
int total_nodes_in_graph;
scanf("%d", &total_nodes_in_graph);
visited.resize(total_nodes_in_graph + 1);
graph g(total_nodes_in_graph + 1);
std::vector<myEdge> vector_all_edges;
for (int i = 1, node1, node2, weight; i < total_nodes_in_graph; ++i) {
scanf("%d %d %d", &node1, &node2, &weight);
g[node1].push_back( {node2, weight} );
g[node2].push_back( {node1, weight} );
vector_all_edges.push_back( {node1, node2, weight} );
}
long long total_sum = 0;
for (auto &e : vector_all_edges) {
visited[e.from] = visited[e.to] = true;
int cc = count_nodes_on_component(g, e.to);
total_sum = (total_sum + cc * (total_nodes_in_graph - cc) * e.weight) % MOD;
visited[e.from] = visited[e.to] = false;
}
printf("%lld\n", total_sum);
}
}
This code takes a lot of time with huge graphs. Is it possible to exploit something to make it run faster?