Pairing graph code giving tle

#1

import java.util.*;
public class Main {
static class Graph {
private class Vertex {// class with a hashmap to hold the neighbours of a vertex and the edge cost
HashMap<String, Integer> nbrs = new HashMap<>();
}

	HashMap<String, Vertex> vtces;// hashmap to store the graph

	public Graph() {
		vtces = new HashMap<>();
	}

	public void addVertex(String vname) {
		Vertex vtx = new Vertex();
		this.vtces.put(vname, vtx);// empty vertex hashmap
	}

	public void addEdge(String vname1, String 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);
	}

	private class Pair {
		String vname;
		String psf;
	}

	public boolean containsEdge(String vname1, String 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 boolean bfs(String src, String dst) {
		HashMap<String, Boolean> processed = new HashMap<>();
		LinkedList<Pair> queue = new LinkedList<>();

		// create a new pair
		Pair sp = new Pair();
		sp.vname = src;
		sp.psf = src;

		// put the new pair in queue
		queue.addLast(sp);
		// while queue is not empty keep on doing the work
		while (!queue.isEmpty()) {

			// remove a pair from queue
			Pair rp = queue.removeFirst();

			if (processed.containsKey(rp.vname)) {
				continue;
			}

			// processed put
			processed.put(rp.vname, true);

			// check for direct edge
			if (containsEdge(rp.vname, dst)) {

// System.out.println(rp.psf + " " + dst);
return true;
}

			// nbrs
			Vertex rpvtx = vtces.get(rp.vname);
			ArrayList<String> nbrs = new ArrayList<>(rpvtx.nbrs.keySet());
			// loop on nbrs
			for (String nbr : nbrs) {
				// process only unprocessed nbrs
				if (!processed.containsKey(nbr)) {
					// make a new pair of nbr and put it in queue
					Pair np = new Pair();
					np.vname = nbr;
					np.psf = rp.psf + " " + nbr;
					queue.addLast(np);
				}
			}
		}
		return false;
	}

	
}

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
	Graph g = new Graph();
	for(int i=0;i<n;i++) {
		g.addVertex(""+i);
	}
	while(m--!=0) {
		g.addEdge(""+sc.nextInt(), ""+sc.nextInt(), 1);
	}
	int a = 0;
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			if(g.bfs(""+i, ""+j)) {
				a++;
			}
		}
	}
	System.out.println(a/2);
}

}

#2

Your code is having a Time Complexity of O(n * n*(n+m)),where n are the number of edges.
Lets see how:As you are using for into for over the size of list wherein list have size=n,and inside n you are calling hasPath which itself have time complexity of n m,
Total=n * n (n+m).
Now we have to do in nlogn or n.
What we can think is,the number of ways of selecting a pair is similar to getting connected components in a Graph .Let me elaborate further,
Consider 5 3
0 1
2 3
0 4

Here,by drawing on paper we can see 4-0-1 and 2-3 are two connected components of size 3 and 2 respectively,hence 3*2 are total ways .
This approach will reduce time complexity to O(m+n).
Please Refer this:https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/