Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int spanningTree(int V, int E, vector<vector<int>> &graph);
- // Driver code
- int main() {
- int t;
- cin >> t;
- while (t--) {
- int V, E;
- cin >> V >> E;
- vector<vector<int> > graph(V, vector<int>(V, 0));
- int i=0;
- while (i++<E) {
- int u, v, w;
- cin >> u >> v >> w;
- u--, v--;
- graph[u][v] = w;
- graph[v][u] = w;
- }
- cout << spanningTree(V, E, graph) << endl;
- }
- return 0;
- }
- // } Driver Code Ends
- typedef pair<int, int> PII;
- // Function to construct and print MST for
- // a graph represented using adjacency
- // matrix representation, with V vertices.
- // graph[i][j] = weight if edge exits else INT_MAX
- bool visited[1000+1];
- int prim(vector<PII> adj[]){
- priority_queue<PII, vector<PII>, greater<PII> > pq;
- int minCost = 0;
- PII p;
- pq.push({0,1});
- while(!pq.empty())
- {
- p=pq.top();
- pq.pop();
- int x = p.second;
- if(visited[x])
- continue;
- minCost += p.first;
- visited[x] = true;
- for(int i=0; i<adj[x].size(); i++)
- {
- int y = adj[x][i].second;
- if(!visited[y])
- pq.push(adj[x][i]);
- }
- }
- return minCost;
- }
- int spanningTree(int V, int E, vector<vector<int>> &graph) {
- // code here
- for(int i=0; i<=V; i++)
- visited[i] = 0;
- vector<PII> adj[V+1];
- for(int i=0; i<V; i++)
- {
- for(int j=i; j<V; j++)
- {
- if(graph[i][j] != 0)
- {
- adj[i+1].push_back(make_pair(graph[i][j],j+1));
- adj[j+1].push_back(make_pair(graph[i][j],i+1));
- }
- }
- }
- return prim(adj);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement