hacktoberfest2020-1/GraphPath.java at master · anish9696/hacktoberfest2020-1 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import java.util.Scanner;
import java.util.ArrayList;
import java.io.File;
import java.io.PrintStream;


class GraphPath{
    static Scanner sc;
    public static void main(String args[]){

        try{
            File file = new File("C:\\Users\\Tanisha\\Desktop\\inputGraph2.txt");
            sc = new Scanner(file);


        }
        catch(Exception e){
            System.out.println("Error");
            System.out.println(e.getMessage());
        }

        String initialInfo;
        if(sc.hasNextLine())
        initialInfo = sc.next();
        else initialInfo = "";
        String[] arr = initialInfo.split(",");
        int n = Integer.parseInt(arr[0]);

        ArrayList<Integer>[] graph = new ArrayList[n];
        for(int i=0; i<n; i++) {
            graph[i] = new ArrayList<>();
        }
        sc.next();
        if(arr[1].equals("u")){
            while (sc.hasNext()){
                String s = sc.next();
                String[] arr1 = s.split(",");
                if(!sc.hasNext()) {
                	boolean[] vis = new boolean[graph.length];

                	try{
                        PrintStream ps = new PrintStream(new File("out2.txt"));
                        PrintStream console = System.out;
                        System.setOut(ps);
                        System.out.println((hasPath((Integer.parseInt(arr1[0])),(Integer.parseInt(arr1[arr1.length-1])),vis,"",graph)?1:0 +" "));
                    }
                    catch(Exception e){
                        System.out.println(e.getMessage());
                    }

                }
                graph[Integer.parseInt(arr1[0])-1].add(Integer.parseInt(arr1[1]));
                graph[Integer.parseInt(arr1[1])-1].add(Integer.parseInt(arr1[0]));
            }
        }
        else if(arr[1].equals("d")){
            while (sc.hasNext()){
                String s = sc.next();
                String[] arr1 = s.split(",");
                if(!sc.hasNext()) {
                	boolean[] vis = new boolean[graph.length];
                	try{
                        PrintStream ps = new PrintStream(new File("graph_Path_out.txt"));
                        PrintStream console = System.out;
                        System.setOut(ps);
                        System.out.println((hasPath((Integer.parseInt(arr1[0])),(Integer.parseInt(arr1[arr1.length-1])),vis,"",graph)?1:0 +" "));
                    }
                    catch(Exception e){
                        System.out.println(e.getMessage());
                    }
                }
                graph[Integer.parseInt(arr1[0])-1]

                		.add(Integer.parseInt(arr1[1]));
            }
        }

        //System.out.println(hasPath(1,4,vis,"",graph));
    }


    public static boolean hasPath(int src, int desti, boolean[] vis, String ans, ArrayList<Integer>[] graph) {

            if (src == desti){
                //System.out.println(ans + " " + desti);
                return true;
            }
            vis[src] = true;
            boolean res = false;
            for (int edge : graph[src]){
                if (!vis[edge])
                    res = res || hasPath(edge, desti, vis, ans + src + " ", graph);
            }

            return res;

    }

}