Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Graph DFS
/**
* @author: Aashish
* Date: 13-07-2019
*/
import java.util.*;
class Solution {
static class Graph {
static Map<Integer, LinkedList<Integer>> adjVertices;
public Graph(int vertices) {
adjVertices = new HashMap<>();
}
public void addVertex(int star) {
adjVertices.putIfAbsent(star, new LinkedList<>());
}
public void addEdge(int star1, int star2) {
adjVertices.get(star1).add(star2);
}
public int dfs(int startStar, boolean[] visited) {
visited[startStar-1] = true;
Iterator<Integer> i = adjVertices.get(startStar).listIterator();
while(i.hasNext()) {
int n = i.next();
if(!visited[n-1]) {
dfs(n, visited);
}
}
//Return the farthest star
return 1;
}
}
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
//input the number of test cases
int numTestCases = scanner.nextInt();
for(int i = 0; i < numTestCases; i++) {
// Input the number of stars
int noOfStars = scanner.nextInt();
Graph graph = new Graph(noOfStars);
for(int j = 0; j < noOfStars - 1; j++) {
int startStar = scanner.nextInt();
int endStar = scanner.nextInt();
graph.addVertex(startStar);
graph.addVertex(endStar);
graph.addEdge(startStar, endStar);
}
// input the brightest star
int brightestStar = scanner.nextInt();
boolean[] visited = new boolean[noOfStars];
int farthestStar = graph.dfs(brightestStar, visited);
System.out.println(farthestStar);
}
scanner.close();
}
}
@aashish-chaubey
Copy link
Author

aashish-chaubey commented Jul 12, 2019

Sample Input:

1
7
5 6
5 2
6 4
6 3
4 7
7 1
5

Sample Output:

1

Problem: Print the last element of the longest path from the start node of the graph

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment