Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2019
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 15.75 KB | None | 0 0
  1. //GRAPH ADJACENCY LIST
  2. class Graph {
  3.     int numberOfVertices;
  4.     ArrayList<Integer>[] adjacencyList;
  5.     public Graph(int numberOfVertices){
  6.         this.numberOfVertices=numberOfVertices;
  7.         adjacencyList=new ArrayList[numberOfVertices];
  8.         for(int i=0;i<numberOfVertices;i++)
  9.             adjacencyList[i]=new ArrayList<>();
  10.     }
  11.  
  12.     public void addEdge(int x,int y){
  13.         adjacencyList[x].add(y);
  14.     }
  15.    
  16.     public ArrayList<Integer> getAdjacentVertices(int x){
  17.         return adjacencyList[x];
  18.     }
  19.    
  20.     public boolean hasEdge(int x,int y){
  21.         return adjacencyList[x].contains(y);
  22.     }
  23.  
  24. //BFS
  25. void bfs(int sourceNode,int numberOfVertices,Graph g) {
  26.         Queue<Integer> vertices=new LinkedList<>();
  27.         int[]pred=new int[numberOfVertices];
  28.         boolean[]visited=new boolean[numberOfVertices];
  29.         int[]distance=new int[numberOfVertices];
  30.         for(int i=0;i<distance.length;i++){
  31.             distance[i]=0;
  32.             pred[i]=-1;
  33.         }
  34.         pred[sourceNode]=-2;
  35.         distance[sourceNode]=0;
  36.         vertices.add(sourceNode);
  37.         while(!vertices.isEmpty()){
  38.             int vertex=vertices.remove();
  39.             System.out.println(vertex+" ");
  40.             for(Integer adjacentVertex:g.adjacent(vertex)){
  41.                 if(!visited[adjacentVertex]){
  42.                     vertices.add(adjacentVertex);
  43.                     pred[adjacentVertex]=vertex;
  44.                     distance[adjacentVertex]++;
  45.                     visited[adjacentVertex]=true;
  46.                 }
  47.             }
  48.         }
  49.  
  50.         //Pred za printanje na pat do dadeno teme..
  51.         //Distance za rastojanie=br rebra od source do toa teme
  52.     }
  53.  
  54. //TOPOLOGICAL REC
  55.     int[] rTopologicalSort(int sourceNode,int numberOfVertices,Graph g){
  56.         boolean[]visited=new boolean[numberOfVertices];
  57.         Stack<Integer>topological = new Stack<>();
  58.         recursiveTopologicalSort(sourceNode,g,topological,visited);
  59.         int topologicalArray[]=new int[numberOfVertices];
  60.         int i=0;
  61.         while(!topological.isEmpty())
  62.             topologicalArray[i++]=topological.pop();
  63.  
  64.         return topologicalArray;
  65.     }
  66.      void recursiveTopologicalSort(int sourceNode,Graph g,Stack<Integer>topological,boolean[]visited){
  67.         visited[sourceNode]=true;
  68.         for (Integer adjacentVertex : g.adjacent(sourceNode)) {
  69.             if (!visited[adjacentVertex]) {
  70.                 recursiveTopologicalSort(adjacentVertex,g,topological,visited);
  71.             }
  72.         }
  73.         topological.push(sourceNode);
  74.     }
  75.  
  76. //DFS REC
  77.     void rDFS(int sourceNode,int numberOfVertices,Graph g){
  78.         boolean[]visited=new boolean[numberOfVertices];
  79.         recursiveDFS(sourceNode,g,visited);
  80.     }
  81.     void recursiveDFS(int sourceNode,Graph g,boolean[]visited){
  82.         visited[sourceNode]=true;
  83.         System.out.println(sourceNode+" ");
  84.         for (Integer adjacentVertex : g.adjacent(sourceNode)) {
  85.             if (!visited[adjacentVertex]) {
  86.                recursiveDFS(adjacentVertex,g,visited);
  87.             }
  88.         }
  89.     }
  90.  
  91. //TOPOLOGICAL REGULAR
  92.     int[] topologicalSort(int sourceNode,int numberOfVertices,Graph g){
  93.         Stack<Integer> vertices=new Stack<>();
  94.         Stack<Integer>topological=new Stack<>();
  95.         boolean[]visited=new boolean[numberOfVertices];
  96.         visited[sourceNode]=true;
  97.         vertices.push(sourceNode);
  98.         while(!vertices.isEmpty()) {
  99.             int vertex = vertices.pop();
  100.             if (g.adjacent(vertex).size == 0)
  101.                 topological.push(vertex);
  102.             else {
  103.                 int count = 0;
  104.                 for (Integer adjacentVertex : g.adjacent(vertex)) {
  105.                     if (!visited[adjacentVertex]) {
  106.                         count++;
  107.                         vertices.push(adjacentVertex);
  108.                         visited[adjacentVertex] = true;
  109.                     }
  110.                 }
  111.                 if(count==0)
  112.                     topological.push(vertex);
  113.             }
  114.         }
  115.         int[]topologicalOrder=new int[numberOfVertices];
  116.         int i=0;
  117.             while(!topological.isEmpty())
  118.                 topologicalOrder[i++]=topological.pop();
  119.  
  120.         return topologicalOrder;
  121.       }
  122.  
  123. //DFS REGULAR
  124.     void dfs(int sourceNode,int numberOfVertices,Graph g) {
  125.         Stack<Integer> vertices=new Stack<>();
  126.         int[]pred=new int[numberOfVertices];
  127.         boolean[]visited=new boolean[numberOfVertices];
  128.         int[]distance=new int[numberOfVertices];
  129.         for(int i=0;i<distance.length;i++){
  130.             distance[i]=0;
  131.             pred[i]=-1;
  132.         }
  133.         pred[sourceNode]=-2;
  134.         distance[sourceNode]=0;
  135.         vertices.push(sourceNode);
  136.         while(!vertices.isEmpty()){
  137.             int vertex=vertices.pop();
  138.             System.out.println(vertex+" ");
  139.             for(Integer adjacentVertex:g.adjacent(vertex)){
  140.                 if(!visited[adjacentVertex]){
  141.                     vertices.push(adjacentVertex);
  142.                     pred[adjacentVertex]=vertex;
  143.                     distance[adjacentVertex]++;
  144.                     visited[adjacentVertex]=true;
  145.                 }
  146.             }
  147.         }
  148.  
  149.         //Pred za printanje na pat do dadeno teme..
  150.         //Distance za rastojanie=br rebra od source do toa teme
  151.     }
  152.  
  153. //CYCLE DETECTION UNDIRECTED
  154. public boolean cycleDetectionUtil(int sourceVertex,boolean[]visited,int parent){
  155.         visited[sourceVertex]=true;
  156.         for(Integer adjacent:getAdjacentVertices(sourceVertex)){
  157.             if(!visited[adjacent]){
  158.                if(cycleDetectionUtil(adjacent,visited,sourceVertex))
  159.                     return true;
  160.             }
  161.             else
  162.                     return parent!=adjacent;  
  163.         }
  164.         return false;
  165.     }
  166.     public boolean cycleDetection(){
  167.         boolean visited[]=new boolean[numberOfVertices];
  168.         for(int i=0;i<numberOfVertices;i++){
  169.             if(!visited[i]) {
  170.                 if (cycleDetectionUtil(i, visited, -1))
  171.                     return true;
  172.             }
  173.         }
  174.         return false;
  175.     }
  176.  
  177. //CYCLE DETECTION DIRECTED
  178.  
  179. public boolean cycleDetection(){
  180.         boolean[]visited=new boolean[numberOfVertices];
  181.         boolean[]backEdge=new boolean[numberOfVertices];
  182.  
  183.         for(int i=0;i<numberOfVertices;i++){
  184.             if(cycleDetectionUtil(i,visited,backEdge))
  185.                 return true;
  186.         }
  187.         return false;
  188.     }
  189.     public boolean cycleDetectionUtil(int sourceVertex,boolean[]visited,boolean[] backEdge){
  190.         if(backEdge[sourceVertex])
  191.             return true;
  192.         if(visited[sourceVertex])
  193.             return false;
  194.  
  195.         visited[sourceVertex]=true;
  196.         backEdge[sourceVertex]=true;
  197.  
  198.         for(Integer adjacent:getAdjacentVertices(sourceVertex)){
  199.             if(cycleDetectionUtil(adjacent,visited,backEdge))
  200.                 return true;
  201.         }
  202.  
  203.         backEdge[sourceVertex]=false;
  204.         return false;
  205.     }
  206.  
  207. //PATH DETECTION
  208.  
  209.  
  210. public boolean isThereAPath(int sourceNode,int endNode){
  211.         Stack<Integer>vertices=new Stack<>();
  212.         Stack<Integer>path=new Stack<>();
  213.         boolean[]visited=new boolean[numberOfVertices];
  214.         int[]pred=new int[numberOfVertices];
  215.         for(int i=0;i<numberOfVertices;i++)
  216.             pred[i]=-1;
  217.         pred[sourceNode]=-2;
  218.         visited[sourceNode]=true;
  219.         vertices.push(sourceNode);
  220.         while(!vertices.isEmpty()){
  221.             int vertex=vertices.pop();
  222.             if(vertex==endNode) {
  223.                 StringBuilder stringBuilder=new StringBuilder();
  224.                 stringBuilder.append("Path: ");
  225.                 int i=endNode;
  226.                 path.push(i);
  227.                 while(i!=-2){
  228.                     path.push(pred[i]);
  229.                     i=pred[i];
  230.                 }
  231.                
  232.                 while(!path.isEmpty())
  233.                     stringBuilder.append(path.pop()).append(" ");
  234.  
  235.                 System.out.println(stringBuilder.toString());
  236.                 return true;
  237.             }
  238.             for(Integer adjacent:getAdjacentVertices(vertex)){
  239.                 if(!visited[adjacent]){
  240.                     visited[adjacent]=true;
  241.                     vertices.push(adjacent);
  242.                     pred[adjacent]=vertex;
  243.                 }
  244.             }
  245.         }
  246.         return false;
  247.     }
  248.  
  249. //BIPARTITE CHECK
  250. public boolean isBipartiteDFS(){
  251.         boolean[]visited=new boolean[numberOfVertices];
  252.         int[]colors=new int[numberOfVertices]; //1 red, -1 blue
  253.         Stack<Integer>vertices=new Stack<>();
  254.         visited[0]=true;
  255.         colors[0]=1;
  256.         vertices.push(0);
  257.         while(!vertices.isEmpty()){
  258.             int vertex=vertices.pop();
  259.             for(Integer adjacent:getAdjacentVertices(vertex)){
  260.                 if(!visited[adjacent]){
  261.                     colors[adjacent]=colors[vertex]*-1;
  262.                     visited[adjacent]=true;
  263.                     vertices.push(adjacent);
  264.                 }else{
  265.                     if(colors[adjacent]==colors[vertex])
  266.                         return false;
  267.                 }
  268.             }
  269.         }
  270.         return true;
  271.     }
  272.  
  273. //STRONGLY connected GRAPH UNDIRECTED - samo proveri dali so bfs/dfs gi posetuvash site teminja
  274. //STRONGLY connected GRAPH DIRECTED - mozhe so floyd da vidish, a mozhe i od sekoe teme dfs i da vidish dali gi posetuva site drugi,
  275. //mozhe i kosaraju algorithm za broj na SCC - pravish DFS na random teme, posle gi reversnuvash site rebra i pak praish dfs od istoto //teme, vrakjash false ako nekoj node ne e stignat
  276.  
  277. //KOSARAJU
  278.  
  279. public boolean dfsCheck(int sourceNode){
  280.         boolean[]visited=new boolean[numberOfVertices];
  281.         visited[sourceNode]=true;
  282.         Stack<Integer>vertices=new Stack<>();
  283.         vertices.push(sourceNode);
  284.         while(!vertices.isEmpty()){
  285.             int vertex=vertices.pop();
  286.             for(Integer adjacent:getAdjacentVertices(vertex)){
  287.                 if(!visited[adjacent]){
  288.                     visited[adjacent]=true;
  289.                     vertices.push(adjacent);
  290.                 }
  291.             }
  292.         }
  293.  
  294.         for(boolean value:visited)
  295.             if(!value)
  296.                 return false;
  297.  
  298.         return true;
  299.     }
  300.     public boolean stronglyConnected(){
  301.         boolean result=dfsCheck(0); //check from source whether you can reach everything
  302.         if(!result)
  303.             return false;
  304.         //switch all arcs
  305.         ArrayList<Integer>[]newAdjacencyList=new ArrayList[numberOfVertices];
  306.         for(int i=0;i<newAdjacencyList.length;i++)
  307.             newAdjacencyList[i]=new ArrayList<>();
  308.        
  309.         for(int i=0;i<adjacencyList.length;i++){
  310.             for(Integer adjacent:adjacencyList[i]){
  311.                 newAdjacencyList[adjacent].add(i);
  312.             }
  313.         }
  314.        
  315.         adjacencyList=newAdjacencyList;
  316.        
  317.         result=dfsCheck(0);
  318.         if(!result)
  319.             return false;
  320.        
  321.         return true;
  322.     }
  323. }
  324.  
  325. //EXAMPLE BFS - dobra zadaca
  326.  
  327.  
  328. import java.io.BufferedReader;
  329. import java.io.IOException;
  330. import java.io.InputStreamReader;
  331. import java.util.*;
  332. class Node{
  333.     String info;
  334.     int index;
  335.     public Node(String info,int index){
  336.         this.index=index;
  337.         this.info=info;
  338.     }
  339. }
  340. class Graph {
  341.     int numberOfVertices;
  342.     ArrayList<Node>[] adjacencyList;
  343.     public Graph(int numberOfVertices){
  344.         this.numberOfVertices=numberOfVertices;
  345.         adjacencyList=new ArrayList[numberOfVertices];
  346.         for(int i=0;i<numberOfVertices;i++)
  347.             adjacencyList[i]=new ArrayList<>();
  348.     }
  349.  
  350.     public void addEdge(Node x,Node y){
  351.         adjacencyList[x.index].add(y);
  352.     }
  353.  
  354.     public ArrayList<Node> getAdjacentVertices(int x){
  355.         return adjacencyList[x];
  356.     }
  357.  
  358.     public boolean hasEdge(Node x,Node y){
  359.         return adjacencyList[x.index].contains(y);
  360.     }
  361. }
  362. public class Mleko{
  363.     public static void main(String[] args) throws IOException {
  364.         BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
  365.         HashMap<String,Integer>mapForVertices=new HashMap<>();
  366.         String firstLineParts[]=bufferedReader.readLine().split("\\s+");
  367.  
  368.         int heightOfSurface=Integer.parseInt(firstLineParts[0]);
  369.         int jump=Integer.parseInt(firstLineParts[1]);
  370.  
  371.         int k=0;
  372.         char[][]grid=new char[2][heightOfSurface];
  373.         for(int i=0;i<2;i++){
  374.             String parts[]=bufferedReader.readLine().split("");
  375.             for (int j = 0; j < heightOfSurface; j++) {
  376.                 char symbol=parts[j].charAt(0);
  377.                 grid[i][j]=symbol;
  378.                 if(symbol=='-'){
  379.                     String location=i+","+j;
  380.                     mapForVertices.put(location,k);
  381.                     k++;
  382.                 }
  383.             }
  384.         }
  385.  
  386.         int numberOfVertices=mapForVertices.size();
  387.         ArrayList<Integer>goalNodes=new ArrayList<>();
  388.         Graph g=new Graph(numberOfVertices);
  389.         for (int i = 0; i < 2; i++) {
  390.             for (int j = 0; j < heightOfSurface; j++) {
  391.                 String location=i+","+j;
  392.                 char symbol=grid[i][j];
  393.                 if(symbol=='-'){
  394.                     int vertex=mapForVertices.get(location);
  395.                     Node node=new Node(location,vertex);
  396.                     if(j+jump>=heightOfSurface||j==heightOfSurface-1)
  397.                         goalNodes.add(vertex);
  398.  
  399.                     if(j>=1&&grid[i][j-1]=='-'){
  400.                         String locationAdd=i+","+(j-1);
  401.                         int adjacentVertex=mapForVertices.get(locationAdd);
  402.                         Node node2=new Node(locationAdd,adjacentVertex);
  403.                         g.addEdge(node,node2);
  404.                     }
  405.                     if(j<=heightOfSurface-2&&grid[i][j+1]=='-'){
  406.                         String locationAdd=i+","+(j+1);
  407.                         int adjacentVertex=mapForVertices.get(locationAdd);
  408.                         Node node2=new Node(locationAdd,adjacentVertex);
  409.                         g.addEdge(node,node2);
  410.                     }
  411.                     if(j<=heightOfSurface-2-jump&&grid[1-i][j+jump]=='-'){
  412.                         String locationAdd=(1-i)+","+(j+jump);
  413.                         int adjacentVertex=mapForVertices.get(locationAdd);
  414.                         Node node2=new Node(locationAdd,adjacentVertex);
  415.                         g.addEdge(node,node2);
  416.                     }
  417.                 }
  418.             }
  419.         }
  420.  
  421.         int sourceNode=0;
  422.  
  423.         boolean[]visited=new boolean[numberOfVertices];
  424.         Queue<Integer>nodes=new LinkedList<>();
  425.         visited[sourceNode]=true;
  426.         boolean solution=false;
  427.         int[]distance=new int[numberOfVertices];
  428.         for (int i = 0; i < distance.length; i++) {
  429.             distance[i]=0;
  430.         }
  431.  
  432.         nodes.add(sourceNode);
  433.         while(!nodes.isEmpty()){
  434.             int node=nodes.remove();
  435.  
  436.             if(goalNodes.contains(node)) {
  437.                 solution = true;
  438.                 break;
  439.             }
  440.  
  441.                 int count=0;
  442.                 for (Node adjacent : g.getAdjacentVertices(node)) {
  443.                     if (!visited[adjacent.index]) {
  444.                         count++;
  445.                         visited[adjacent.index] = true;
  446.                         String location = adjacent.info;
  447.                         distance[adjacent.index]+=1;
  448.                         String[] parts = location.split(",");
  449.                         int y = Integer.parseInt(parts[1]);
  450.                         if (y >= distance[adjacent.index]) {
  451.                             nodes.add(adjacent.index);
  452.                         }
  453.                     }
  454.                 }
  455.             }
  456.         if(solution)
  457.             System.out.println("yes");
  458.         else
  459.             System.out.println("no");
  460.     }
  461. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement