My code : -
import java.util.Scanner;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.HashMap;
public class Main {
public static void main(String args[]) {
Scanner scn = new Scanner(System.in);
int t = scn.nextInt();
while(t>0){
Graph graph = new Graph();
int n = scn.nextInt();
int m = scn.nextInt();
int costt = scn.nextInt();
int costr = scn.nextInt();
for(int i=1;i<=n;i++){
graph.addvertex(i);
}
while(m>0){
int a = scn.nextInt();
int b = scn.nextInt();
graph.addedge(a,b,costr);
m–;
}
if(costt<costr){
System.out.println(costtn);
}else{
int components=graph.countconnected();
int noofroads=n-components;
int alonevertices=graph.noedge();
long ans = costtcomponents + costrnoofroads + costtalonevertices;
System.out.println(ans);
}
t–;
}
}
}
class Graph{
private class Vertex{
HashMap<Integer,Integer> nbrs = new HashMap<>();
}
HashMap<Integer,Vertex> vtces;
Graph(){
vtces = new HashMap<>();
}
public int numvertex(){
return this.vtces.size();
}
public boolean containsvertex(int vname){
return this.vtces.containsKey(vname);
}
public void addvertex(int vname){
if(vtces.containsKey(vname)){
return;
}
Vertex vtx = new Vertex();
vtces.put(vname,vtx);
}
public void removevertex(int vname){
Vertex vtx = vtces.get(vname);
ArrayList keys = new ArrayList<>(vtx.nbrs.keySet());
for(Integer key : keys){
Vertex nbrvtx = vtces.get(key);
nbrvtx.nbrs.remove(vname);
}
}
public int numedges(){
int count=0;
ArrayList keys = new ArrayList<>(vtces.keySet());
for(int key : keys){
Vertex vtx = vtces.get(key);
count+=vtx.nbrs.size();
}
return count/2;
}
public boolean containsedge(int vname1,int vname2){
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if(vtx1==null||vtx2==null||!vtx1.nbrs.containsKey(vname2)){
return false;
}
return true;
}
public void addedge(int vname1,int vname2,int cost){
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if(vtx1==null||vtx2==null||vtx1.nbrs.containsKey(vname2)){
return;
}
vtx1.nbrs.put(vname2,cost);
vtx2.nbrs.put(vname1,cost);
}
public void removeedge(int vname1,int vname2){
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if(vtx1==null||vtx2==null||!vtx1.nbrs.containsKey(vname2)){
return;
}
vtx1.nbrs.remove(vname2);
vtx2.nbrs.remove(vname1);
}
public void display(){
ArrayList keys = new ArrayList<>(vtces.keySet());
for(int key : keys){
Vertex vtx = vtces.get(key);
System.out.println(key + " : "+ vtx.nbrs);
}
}
private class Pair{
int vname;
int psf;
}
public int countconnected(){
int flag=0;
HashMap<Integer,Boolean> processed = new HashMap<>();
LinkedList queue = new LinkedList<>();
ArrayList keys = new ArrayList<>(vtces.keySet());
for(int key : keys){
if(processed.containsKey(key)){
continue;
}
flag++;
Pair sp = new Pair();
sp.vname=key;
sp.psf=key;
queue.addLast(sp);
while(!queue.isEmpty()){
Pair rp = queue.removeFirst();
if(processed.containsKey(rp.vname)){
continue;
}
processed.put(rp.vname,true);
Vertex rpvtx = vtces.get(rp.vname);
ArrayList nbrs = new ArrayList<>(rpvtx.nbrs.keySet());
for(Integer nbr : nbrs){
if(!processed.containsKey(nbr)){
Pair np = new Pair();
np.vname=nbr;
np.psf=rp.psf+vtces.get(rp.vname).nbrs.get(nbr);
queue.addLast(np);
}
}
}
}
return flag;
}
public int noedge(){
int count=0;
ArrayList keys = new ArrayList<>(vtces.keySet());
for(int key : keys){
Vertex vtx = vtces.get(key);
if(vtx.nbrs.size()==0){
count++;
}
}
return count;
}
}
Religious people challenge test cases wrong
On line 25, the code should be costt*n similarly on line 30 it should be long ans = costt*components + costr*noofroads + costt*alonevertices;
Please apply these changes and see if it helps as I do not see any issue logic wise
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.