We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
importjava.io.*;importjava.util.*;//we use adjacency list representation of a DAGclassGraph{intvertices;//no of vertices//ArrayList<Integer> reachable = new ArrayList<>();longa[]=newlong[10];//a value of all the verticesLinkedList<Integer>[]l1=newLinkedList[10];booleanvisited[]=newboolean[10];Graph(intvertices){this.vertices=vertices;for(inti=0;i<vertices;i++){l1[i]=newLinkedList<Integer>();l1[i].add(i);//a vertex is reachable from itselfvisited[i]=false;}}voidaddEdge(intv1,intv2){l1[v1].add(v2);//since directed}voiddo_dfs_1(intv1,longx)//dfs for 1st type of instruction{/** for(int i=0;i<l1[v1].size();i++) System.out.print(l1[v1].get(i) + " "); */visited[v1]=true;a[v1]=x;//System.out.print(v1 + " ");for(inti=0;i<l1[v1].size();i++){if(visited[l1[v1].get(i)]==false){visited[l1[v1].get(i)]=true;//System.out.print(l1[v1].get(i)+ " ");do_dfs_1(l1[v1].get(i),x);}//set to x even if truea[l1[v1].get(i)]=x;}}voiddo_dfs_2(intv1,longx)//dfs for 1st type of instruction{/** for(int i=0;i<l1[v1].size();i++) System.out.print(l1[v1].get(i) + " "); */visited[v1]=true;if(a[v1]>x)a[v1]=x;//System.out.print(v1 + " ");for(inti=0;i<l1[v1].size();i++){if(visited[l1[v1].get(i)]==false){visited[l1[v1].get(i)]=true;//System.out.print(l1[v1].get(i)+ " ");do_dfs_2(l1[v1].get(i),x);}if(a[l1[v1].get(i)]>x)a[l1[v1].get(i)]=x;}}}publicclassSolution{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();//no of verticesintm=sc.nextInt();//no of edgesintq=sc.nextInt();//no of queriesArrayList<Long>ans=newArrayList<>();//there are three types of queries/** * Type 1:- 1 u x where all the nodes v reachable from u have their av turned to x(a vertex is reachable from itself) * Type 2:- 2 u x where all the nodes v reachble from u have their av turned to x(if av>x) * Type 3: 3 u which will print the av value of u */Graphg1=newGraph(n);inta[]=newint[n];for(inti=0;i<m;i++){intstart=sc.nextInt();intend=sc.nextInt();g1.addEdge(start-1,end-1);}//now for instructionsfor(intk=0;k<q;k++){inttype=sc.nextInt();if(type==1){intsource=sc.nextInt();longx=sc.nextLong();//all reachable to x/** for(int l=0;l<g1.l1[source-1].size();l++) { a[g1.l1[source-1].get(l)]=x; } */g1.do_dfs_1(source-1,x);}if(type==2){intsource=sc.nextInt();longx=sc.nextLong();g1.do_dfs_2(source-1,x);}if(type==3){intsource=sc.nextInt();ans.add(g1.a[source-1]);//System.out.print(a[source]);}}for(inti=0;i<ans.size();i++){System.out.println(ans.get(i));}}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
DAG Queries
You are viewing a single comment's thread. Return to all comments →