I don't understand of this question

#1

can you explain this question with the example and tell me
can solve with Adjacency List or adjacency matrix

#2

@sksumitkumardiwaker
Count the number of disjoint components (subgraphs which are not connected to each other) and store them in a variable , say ‘components’ Each component must have a single Temple So cost of temple in each component is A * components Further there are (x-1) roads required in each component where x is no of vertices in that component Sum of roads in all components = (n - components) , n is no of nodes in adjacency list Multiply that with B , cost to repair each road Cost so far , cost = A*component + B * (n-components)

But there are some vertices that do not form any edges Some vertices which stand alone and each of these vertices must have a temple of its own Since they do not form any edge , there count is not included in the adjacency list No of such nodes is (V - n) …where V is total no of nodes and n is no of nodes that form an edge and are part of previously counted components Since each of these nodes must have a temple Total cost = A components + B (n-component) + A*(V-n)

Do not forget to consider the base case when A<=B. If cost of constructing temples in each city is less than repairing roads , simply build temples in all cities and return V*A .

#3

can you explain with example

#4

@sksumitkumardiwaker
like ex
1 2
2 3
3 4
5 6
temple cost 5 road cost 2
so u can make temple in city 1 and city have path to city 1 are 2 ,3 and 4
so cost =5+2*3=11
also u have to make temple at city 5 as no path b|w city 1 and 5
but city 6 is connect to 5
so cost=5+2=7
total=18
Basically u have to find component of graph

#5

can you provide me code

#6

@sksumitkumardiwaker
import java.util.*;

public class Main{
public static void main(String args[]) {
StringBuilder str = new StringBuilder();
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int f = 0; f < t; f++) {
Graph g = new Graph();
int nv = sc.nextInt();
int ne = sc.nextInt();
for (int i = 0; i < nv; i++) {
g.addVertex("" + (i + 1));
}
int pv = sc.nextInt();
int pe = sc.nextInt();
for (int i = 1; i <= ne; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
g.addEdge(v1 + “”, v2 + “”, 1);
}
g.setPv(pv);
g.setPe(pe);
long a = g.totCost();
str.append(a);
str.append("\n");
}
System.out.print(str);
}
}

class Graph {
HashMap<String, Vertex> vtces;

private class Vertex {
HashMap<String, Integer> nbrs;

Vertex() {
	nbrs = new HashMap<String, Integer>();
}

}

Graph() {
vtces = new HashMap<String, Vertex>();
}

// Total vertex in Graph

public int numVertex() {
return this.vtces.size();
}

// Add a Vertex

public void addVertex(String vname) {
Vertex vtx = new Vertex();
if (this.vtces.containsKey(vname))
return;
else
this.vtces.put(vname, vtx);
}

// Contains a vertex

public boolean containsVertex(String vname) {
return vtces.containsKey(vname);
}

// Total Edges in a graph.

public int numEdges() {
Set set = vtces.keySet();
int sum = 0;
for (String key : set) {
sum += vtces.get(key).nbrs.size();
}
return sum / 2;
}

// Add an Edge

public void addEdge(String vname1, String vname2, int cost) {
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if (vtx1 != null && vtx2 != null) {
if (vtx1.nbrs.containsKey(vname2) && vtx2.nbrs.containsKey(vname1)) {
return;

	} else {
		vtx1.nbrs.put(vname2, cost);
		vtx2.nbrs.put(vname1, cost);
	}
}

}

// Contains Edge

public boolean containsEdge(String vname1, String vname2) {
return vtces.get(vname1).nbrs.containsKey(vname2);
}

int pv;
int pe;

public void setPv(int pv) {
this.pv = pv;
}

public void setPe(int pe) {
this.pe = pe;
}

public long totCost() {
Stack stack = new Stack<>();
Set set = vtces.keySet();
HashMap<String, Integer> visited = new HashMap<String, Integer>();
for (String key : set) {
stack.push(key);
}
long sum = 0;
int prevSize = 0;
for (int i = 0; i < vtces.size(); i++) {
String str = stack.pop();
if (visited.containsKey(str)) {
continue;
} else {
dfs(str, visited);
int a = visited.size() - prevSize;
prevSize = visited.size();
if (pv > pe) {
sum += pv + pe*1L * (a - 1);
} else {
sum += pv 1L a;
}
}
}
return sum;
}

private void dfs(String str, HashMap<String, Integer> visited) {
visited.put(str, 1);
Set set = vtces.get(str).nbrs.keySet();
for (String key : set) {
if (!visited.containsKey(key)) {
dfs(key, visited);
}
}
}
}

#7

@sksumitkumardiwaker
use above code as reference only try to implement on your own.

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.