Untitled
unknown
plain_text
2 years ago
2.0 kB
5
Indexable
import java.util.*; class Solution { public void DFSTraversal(List<List<Integer>> edges, int n) { // Write your code here boolean[] visited = new boolean[n]; ArrayList<Integer>[] adjList = new ArrayList[n]; for (int i = 0; i < adjList.length; i++) { adjList[i] = new ArrayList<>(); } for (List<Integer> l : edges) { adjList[l.get(0)].add(l.get(1)); adjList[l.get(1)].add(l.get(0)); // add the edge in both directions for an undirected graph } for (int i = 0; i < adjList.length; i++) { Collections.sort(adjList[i]); Collections.reverse(adjList[i]); } Stack<Integer> stk = new Stack<>(); for (int i = 0; i < n; i++) { // iterate over all nodes if (!visited[i]) { // check if the node has already been visited stk.push(i); while (!stk.isEmpty()) { int start = stk.pop(); if (!visited[start]) { System.out.print(start + " "); visited[start] = true; } for (int j = 0; j < adjList[start].size(); j++) { int neighbor = adjList[start].get(j); if (!visited[neighbor]) { stk.push(neighbor); } } } } } } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int e = sc.nextInt(); List<List<Integer>> ed = new ArrayList<>(); for (int i = 0; i < e; i++) { List<Integer> l = new ArrayList<>(); l.add(sc.nextInt()); l.add(sc.nextInt()); ed.add(l); } Solution ob = new Solution(); ob.DFSTraversal(ed, n); } }
Editor is loading...