Created
July 12, 2019 23:32
-
-
Save aashish-chaubey/646275b468df646014d3ba53b6513bc1 to your computer and use it in GitHub Desktop.
Graph DFS
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* @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(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Sample Input:
Sample Output:
Problem: Print the last element of the longest path from the start node of the graph