Problem Statement
It is required to calculate the shortest distance from start position (Node S) to all of the other nodes in the graph.
Note 1: If a node is unreachable , the distance is assumed as .
Note 2: The length of each edge in the graph is units.
Input Format
The first line contains , denoting the number of test cases.
First line of each test case has two integers , denoting the number of nodes in the graph and , denoting the number of edges in the graph.
The next lines each consist of two space separated integers , where and denote the two nodes between which the edge exists.
The last line of a testcase has an integer , denoting the starting position.
Constraints
Output Format
For each of test cases, print a single line consisting of space-separated integers, denoting the shortest distances of the N-1 nodes from starting position . This will be done for all nodes same as in the order of input 1 to N.
For unreachable nodes, print .
Sample Input
2
4 2
1 2
1 3
1
3 1
2 3
2
Sample Output
6 6 -1
-1 6
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.concurrent.ArrayBlockingQueue;
public class Solution {
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i=0;i<t;i++)
{
int n = sc.nextInt();
Map<String,Node> nodes = createNodes(n);
int e = sc.nextInt();
Set<Node> reachable = new HashSet<Node>();
for(int k=0;k<e;k++)
{
String start = sc.next();
String end = sc.next();
Node st = nodes.get(start);
Node en = nodes.get(end);
st.addToLinks(en);
en.addToLinks(st);
reachable.add(st);
reachable.add(en);
}
String startNde = sc.next();
Node startNode = nodes.get(startNde);
getShortestPath(startNode, nodes,reachable);
System.out.println();
}
/*Node one = new Node("1");
Node two = new Node("2");
Node three = new Node("3");
Node four = new Node("4");
Node five = new Node("5");
one.addToLinks(two);
one.addToLinks(three);
three.addToLinks(four);
four.addToLinks(five);
System.out.println(four.search(one));*/
}
public static Map<String,Node> createNodes(int n)
{
Map<String,Node> nodeMap = new LinkedHashMap<String,Node>();
for(int i=1;i<=n;i++)
{
nodeMap.put(i+"", new Node(i+""));
}
return nodeMap;
}
public static void getShortestPath(Node s,Map<String,Node> nodes,Set<Node> existing)
{
for(Node n:nodes.values())
{
if(n.equals(s))
continue;
else if(!existing.contains(n)){
System.out.print(-1+" ");
}
else
{
s.setLength(0);
ArrayBlockingQueue<Node> q = s.getQueue();
q.clear();
q.add(s);
int l=s.searchBFS(n);
if(l>0)
System.out.print(l*6+" ");
else
System.out.print(-1+" ");
}
setTraversedForAll(existing);
}
}
public static void setTraversedForAll(Set<Node> reachable)
{
for(Node n:reachable)
{
n.setTraversed(false);
}
}
}
class Node {
private String name;
private Set<Node> links = new HashSet<Node>();
private boolean isTraversed = false;
public Node(String name)
{
this.name = name;
}
public boolean isTraversed() {
return isTraversed;
}
public void setTraversed(boolean isTraversed) {
this.isTraversed = isTraversed;
}
public void addToLinks(Node link)
{
links.add(link);
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
private ArrayBlockingQueue<Node> queue = new ArrayBlockingQueue<>(10000);
private int length = 0;
public ArrayBlockingQueue<Node> getQueue() {
return queue;
}
public void setQueue(ArrayBlockingQueue<Node> queue) {
this.queue = queue;
}
public int getLength() {
return length;
}
public void setLength(int length) {
this.length = length;
}
public int searchBFS(Node f)
{
Node s = queue.poll();
while(s!=null)
{
if(s.isTraversed==true)
{
s=queue.poll();
continue;
}
// System.out.println("name---"+s.name);
if(s.links.contains(f))
{
if(s.length==0)
return 1;
return s.length+1;
}
else{
//length++;
}
if(s.links.size()>0)
{
s.isTraversed= true;
queue.addAll(s.links);
addLength(s.links,s);
//length++;
}
else
{
s.isTraversed= true;
s = queue.poll();
continue;
}
s = queue.poll();
}
return 0;
}
public void addLength(Set<Node> n,Node s)
{
for(Node e:n)
{
if(e.getLength()==0)
e.setLength(s.length+1);
}
}
public int search(Node f,Node start)
{
//System.out.println("print- "+f.name+"- this -"+this.name);
if(links.contains(f))
{
return 1;
}
int sl = 0;
if(this.isTraversed==true)
return sl;
for(Node n:this.links)
{
this.isTraversed=true;
if(n.equals(start))
continue;
int k = n.search(f,this);
if(k>0){
int l = 1 + k;
if(sl==0)
{
sl = l;
}else if(l<sl)
{
sl = l;
}
if(sl==2)
{
return sl;
}
}
}
return sl;
}
}