Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
2
Indexable
Never
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);
    }
}