Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package acm;
- import java.util.*;
- import java.io.*;
- public class GraphTraversal {
- public static void main(String[] args) throws IOException {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- String testCases = (br.readLine());
- //while (testCases!="") {
- int totalNodes;
- int totalEdges;
- String ne = br.readLine();
- totalNodes = Integer.parseInt(ne.split(" ")[0]);
- totalEdges = Integer.parseInt(ne.split(" ")[1]);
- LinkedList<LinkedList> graphInfo = new LinkedList<LinkedList>();
- for(int i=0;i<totalNodes;i++){
- LinkedList al=new LinkedList();
- graphInfo.add(i,al);
- }
- int edge = 1;
- String aPlusB = br.readLine();
- int root=Integer.parseInt(aPlusB.split(" ")[0]);
- while (edge <= totalEdges) {
- int A = Integer.parseInt(aPlusB.split(" ")[0]);
- int B = Integer.parseInt(aPlusB.split(" ")[1]);
- processGraphInfo(graphInfo, A, B);
- aPlusB = br.readLine();
- edge++;
- }
- for (int i = 0; i < graphInfo.size(); i++) {
- LinkedList al = graphInfo.get(i);
- Collections.sort(al);
- }
- System.out.println(testCases);
- //Breadth First;
- Queue q=new LinkedList();
- q.add((Integer)root);
- for(int i=0;i<graphInfo.size();i++){
- LinkedList ll=(LinkedList)graphInfo.get(i);
- for(int j=0;j<ll.size();j++){
- Integer num=(Integer)ll.get(j);
- if(q.contains(num)){
- continue;
- }else{
- q.add(num);
- }
- }
- }
- int i=1;
- int queueSize=q.size();
- while(!q.isEmpty()){
- if(i==queueSize){
- System.out.print(q.poll());
- }else{
- System.out.print(q.poll()+", ");
- }
- i++;
- }
- System.out.println("");
- //Depth First
- Stack stk=new Stack();
- int j=0;
- while(true){
- for(int i1=0;i1<graphInfo.size();i1++){
- LinkedList ll=(LinkedList)graphInfo.get(i1);
- for(int i2=j;i2<ll.size();i2++){
- Integer num=(Integer)ll.get(i2);
- if(root!=num && !stk.contains(num)){
- stk.add(num);
- break;
- }else{
- continue;
- }
- }
- }
- if(stk.size()!=(totalNodes-1)){
- j++;
- }else if(stk.size()==(totalNodes-1)){
- stk.add(root);
- break;
- }
- }
- while(!q.isEmpty()){
- if(i==queueSize){
- System.out.print(q.poll());
- }else{
- System.out.print(q.poll()+", ");
- }
- i++;
- }
- while(!stk.isEmpty()){
- if(stk.size()==1){
- System.out.print(stk.pop());
- }else{
- System.out.print(stk.pop()+", ");
- }
- }
- // testCases = (br.readLine());
- //}
- }
- // Adjacency List
- public static void processGraphInfo(LinkedList ll, int a, int b) {
- LinkedList tmpA=(LinkedList)ll.get(a);
- LinkedList tmpB=(LinkedList)ll.get(b);
- tmpA.add(b);
- tmpB.add(a);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement