Religious people problem Graphs . Please Check why it is giving wrong answer

#1

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);
int 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<String> 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 int totCost(){
    Stack<String> stack=new Stack<>();
    Set<String> set=vtces.keySet();
    HashMap<String,Integer> visited=new HashMap<String,Integer>();
    for(String key:set){
        stack.push(key);
    }
    int 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*(a-1);
            }
            else{
                sum+=pv*a;
            }
        }
    }
    return sum;
}

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

}

#2

@Anubhav44044
your code is correct buddy you just need to take sum as long variable
import java.util.*;

public class testing {
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<String> 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<String> stack = new Stack<>();
	Set<String> 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<String> set = vtces.get(str).nbrs.keySet();
	for (String key : set) {
		if (!visited.containsKey(key)) {
			dfs(key, visited);
		}
	}
}

}

here is your code with just few modification
if you have any doubt feel free to ask otherwise mark this as resolved in my doubts section and rate me as well. :blush: :blush: