Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //GRAPH ADJACENCY LIST
- class Graph {
- int numberOfVertices;
- ArrayList<Integer>[] adjacencyList;
- public Graph(int numberOfVertices){
- this.numberOfVertices=numberOfVertices;
- adjacencyList=new ArrayList[numberOfVertices];
- for(int i=0;i<numberOfVertices;i++)
- adjacencyList[i]=new ArrayList<>();
- }
- public void addEdge(int x,int y){
- adjacencyList[x].add(y);
- }
- public ArrayList<Integer> getAdjacentVertices(int x){
- return adjacencyList[x];
- }
- public boolean hasEdge(int x,int y){
- return adjacencyList[x].contains(y);
- }
- //BFS
- void bfs(int sourceNode,int numberOfVertices,Graph g) {
- Queue<Integer> vertices=new LinkedList<>();
- int[]pred=new int[numberOfVertices];
- boolean[]visited=new boolean[numberOfVertices];
- int[]distance=new int[numberOfVertices];
- for(int i=0;i<distance.length;i++){
- distance[i]=0;
- pred[i]=-1;
- }
- pred[sourceNode]=-2;
- distance[sourceNode]=0;
- vertices.add(sourceNode);
- while(!vertices.isEmpty()){
- int vertex=vertices.remove();
- System.out.println(vertex+" ");
- for(Integer adjacentVertex:g.adjacent(vertex)){
- if(!visited[adjacentVertex]){
- vertices.add(adjacentVertex);
- pred[adjacentVertex]=vertex;
- distance[adjacentVertex]++;
- visited[adjacentVertex]=true;
- }
- }
- }
- //Pred za printanje na pat do dadeno teme..
- //Distance za rastojanie=br rebra od source do toa teme
- }
- //TOPOLOGICAL REC
- int[] rTopologicalSort(int sourceNode,int numberOfVertices,Graph g){
- boolean[]visited=new boolean[numberOfVertices];
- Stack<Integer>topological = new Stack<>();
- recursiveTopologicalSort(sourceNode,g,topological,visited);
- int topologicalArray[]=new int[numberOfVertices];
- int i=0;
- while(!topological.isEmpty())
- topologicalArray[i++]=topological.pop();
- return topologicalArray;
- }
- void recursiveTopologicalSort(int sourceNode,Graph g,Stack<Integer>topological,boolean[]visited){
- visited[sourceNode]=true;
- for (Integer adjacentVertex : g.adjacent(sourceNode)) {
- if (!visited[adjacentVertex]) {
- recursiveTopologicalSort(adjacentVertex,g,topological,visited);
- }
- }
- topological.push(sourceNode);
- }
- //DFS REC
- void rDFS(int sourceNode,int numberOfVertices,Graph g){
- boolean[]visited=new boolean[numberOfVertices];
- recursiveDFS(sourceNode,g,visited);
- }
- void recursiveDFS(int sourceNode,Graph g,boolean[]visited){
- visited[sourceNode]=true;
- System.out.println(sourceNode+" ");
- for (Integer adjacentVertex : g.adjacent(sourceNode)) {
- if (!visited[adjacentVertex]) {
- recursiveDFS(adjacentVertex,g,visited);
- }
- }
- }
- //TOPOLOGICAL REGULAR
- int[] topologicalSort(int sourceNode,int numberOfVertices,Graph g){
- Stack<Integer> vertices=new Stack<>();
- Stack<Integer>topological=new Stack<>();
- boolean[]visited=new boolean[numberOfVertices];
- visited[sourceNode]=true;
- vertices.push(sourceNode);
- while(!vertices.isEmpty()) {
- int vertex = vertices.pop();
- if (g.adjacent(vertex).size == 0)
- topological.push(vertex);
- else {
- int count = 0;
- for (Integer adjacentVertex : g.adjacent(vertex)) {
- if (!visited[adjacentVertex]) {
- count++;
- vertices.push(adjacentVertex);
- visited[adjacentVertex] = true;
- }
- }
- if(count==0)
- topological.push(vertex);
- }
- }
- int[]topologicalOrder=new int[numberOfVertices];
- int i=0;
- while(!topological.isEmpty())
- topologicalOrder[i++]=topological.pop();
- return topologicalOrder;
- }
- //DFS REGULAR
- void dfs(int sourceNode,int numberOfVertices,Graph g) {
- Stack<Integer> vertices=new Stack<>();
- int[]pred=new int[numberOfVertices];
- boolean[]visited=new boolean[numberOfVertices];
- int[]distance=new int[numberOfVertices];
- for(int i=0;i<distance.length;i++){
- distance[i]=0;
- pred[i]=-1;
- }
- pred[sourceNode]=-2;
- distance[sourceNode]=0;
- vertices.push(sourceNode);
- while(!vertices.isEmpty()){
- int vertex=vertices.pop();
- System.out.println(vertex+" ");
- for(Integer adjacentVertex:g.adjacent(vertex)){
- if(!visited[adjacentVertex]){
- vertices.push(adjacentVertex);
- pred[adjacentVertex]=vertex;
- distance[adjacentVertex]++;
- visited[adjacentVertex]=true;
- }
- }
- }
- //Pred za printanje na pat do dadeno teme..
- //Distance za rastojanie=br rebra od source do toa teme
- }
- //CYCLE DETECTION UNDIRECTED
- public boolean cycleDetectionUtil(int sourceVertex,boolean[]visited,int parent){
- visited[sourceVertex]=true;
- for(Integer adjacent:getAdjacentVertices(sourceVertex)){
- if(!visited[adjacent]){
- if(cycleDetectionUtil(adjacent,visited,sourceVertex))
- return true;
- }
- else
- return parent!=adjacent;
- }
- return false;
- }
- public boolean cycleDetection(){
- boolean visited[]=new boolean[numberOfVertices];
- for(int i=0;i<numberOfVertices;i++){
- if(!visited[i]) {
- if (cycleDetectionUtil(i, visited, -1))
- return true;
- }
- }
- return false;
- }
- //CYCLE DETECTION DIRECTED
- public boolean cycleDetection(){
- boolean[]visited=new boolean[numberOfVertices];
- boolean[]backEdge=new boolean[numberOfVertices];
- for(int i=0;i<numberOfVertices;i++){
- if(cycleDetectionUtil(i,visited,backEdge))
- return true;
- }
- return false;
- }
- public boolean cycleDetectionUtil(int sourceVertex,boolean[]visited,boolean[] backEdge){
- if(backEdge[sourceVertex])
- return true;
- if(visited[sourceVertex])
- return false;
- visited[sourceVertex]=true;
- backEdge[sourceVertex]=true;
- for(Integer adjacent:getAdjacentVertices(sourceVertex)){
- if(cycleDetectionUtil(adjacent,visited,backEdge))
- return true;
- }
- backEdge[sourceVertex]=false;
- return false;
- }
- //PATH DETECTION
- public boolean isThereAPath(int sourceNode,int endNode){
- Stack<Integer>vertices=new Stack<>();
- Stack<Integer>path=new Stack<>();
- boolean[]visited=new boolean[numberOfVertices];
- int[]pred=new int[numberOfVertices];
- for(int i=0;i<numberOfVertices;i++)
- pred[i]=-1;
- pred[sourceNode]=-2;
- visited[sourceNode]=true;
- vertices.push(sourceNode);
- while(!vertices.isEmpty()){
- int vertex=vertices.pop();
- if(vertex==endNode) {
- StringBuilder stringBuilder=new StringBuilder();
- stringBuilder.append("Path: ");
- int i=endNode;
- path.push(i);
- while(i!=-2){
- path.push(pred[i]);
- i=pred[i];
- }
- while(!path.isEmpty())
- stringBuilder.append(path.pop()).append(" ");
- System.out.println(stringBuilder.toString());
- return true;
- }
- for(Integer adjacent:getAdjacentVertices(vertex)){
- if(!visited[adjacent]){
- visited[adjacent]=true;
- vertices.push(adjacent);
- pred[adjacent]=vertex;
- }
- }
- }
- return false;
- }
- //BIPARTITE CHECK
- public boolean isBipartiteDFS(){
- boolean[]visited=new boolean[numberOfVertices];
- int[]colors=new int[numberOfVertices]; //1 red, -1 blue
- Stack<Integer>vertices=new Stack<>();
- visited[0]=true;
- colors[0]=1;
- vertices.push(0);
- while(!vertices.isEmpty()){
- int vertex=vertices.pop();
- for(Integer adjacent:getAdjacentVertices(vertex)){
- if(!visited[adjacent]){
- colors[adjacent]=colors[vertex]*-1;
- visited[adjacent]=true;
- vertices.push(adjacent);
- }else{
- if(colors[adjacent]==colors[vertex])
- return false;
- }
- }
- }
- return true;
- }
- //STRONGLY connected GRAPH UNDIRECTED - samo proveri dali so bfs/dfs gi posetuvash site teminja
- //STRONGLY connected GRAPH DIRECTED - mozhe so floyd da vidish, a mozhe i od sekoe teme dfs i da vidish dali gi posetuva site drugi,
- //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
- //KOSARAJU
- public boolean dfsCheck(int sourceNode){
- boolean[]visited=new boolean[numberOfVertices];
- visited[sourceNode]=true;
- Stack<Integer>vertices=new Stack<>();
- vertices.push(sourceNode);
- while(!vertices.isEmpty()){
- int vertex=vertices.pop();
- for(Integer adjacent:getAdjacentVertices(vertex)){
- if(!visited[adjacent]){
- visited[adjacent]=true;
- vertices.push(adjacent);
- }
- }
- }
- for(boolean value:visited)
- if(!value)
- return false;
- return true;
- }
- public boolean stronglyConnected(){
- boolean result=dfsCheck(0); //check from source whether you can reach everything
- if(!result)
- return false;
- //switch all arcs
- ArrayList<Integer>[]newAdjacencyList=new ArrayList[numberOfVertices];
- for(int i=0;i<newAdjacencyList.length;i++)
- newAdjacencyList[i]=new ArrayList<>();
- for(int i=0;i<adjacencyList.length;i++){
- for(Integer adjacent:adjacencyList[i]){
- newAdjacencyList[adjacent].add(i);
- }
- }
- adjacencyList=newAdjacencyList;
- result=dfsCheck(0);
- if(!result)
- return false;
- return true;
- }
- }
- //EXAMPLE BFS - dobra zadaca
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.*;
- class Node{
- String info;
- int index;
- public Node(String info,int index){
- this.index=index;
- this.info=info;
- }
- }
- class Graph {
- int numberOfVertices;
- ArrayList<Node>[] adjacencyList;
- public Graph(int numberOfVertices){
- this.numberOfVertices=numberOfVertices;
- adjacencyList=new ArrayList[numberOfVertices];
- for(int i=0;i<numberOfVertices;i++)
- adjacencyList[i]=new ArrayList<>();
- }
- public void addEdge(Node x,Node y){
- adjacencyList[x.index].add(y);
- }
- public ArrayList<Node> getAdjacentVertices(int x){
- return adjacencyList[x];
- }
- public boolean hasEdge(Node x,Node y){
- return adjacencyList[x.index].contains(y);
- }
- }
- public class Mleko{
- public static void main(String[] args) throws IOException {
- BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
- HashMap<String,Integer>mapForVertices=new HashMap<>();
- String firstLineParts[]=bufferedReader.readLine().split("\\s+");
- int heightOfSurface=Integer.parseInt(firstLineParts[0]);
- int jump=Integer.parseInt(firstLineParts[1]);
- int k=0;
- char[][]grid=new char[2][heightOfSurface];
- for(int i=0;i<2;i++){
- String parts[]=bufferedReader.readLine().split("");
- for (int j = 0; j < heightOfSurface; j++) {
- char symbol=parts[j].charAt(0);
- grid[i][j]=symbol;
- if(symbol=='-'){
- String location=i+","+j;
- mapForVertices.put(location,k);
- k++;
- }
- }
- }
- int numberOfVertices=mapForVertices.size();
- ArrayList<Integer>goalNodes=new ArrayList<>();
- Graph g=new Graph(numberOfVertices);
- for (int i = 0; i < 2; i++) {
- for (int j = 0; j < heightOfSurface; j++) {
- String location=i+","+j;
- char symbol=grid[i][j];
- if(symbol=='-'){
- int vertex=mapForVertices.get(location);
- Node node=new Node(location,vertex);
- if(j+jump>=heightOfSurface||j==heightOfSurface-1)
- goalNodes.add(vertex);
- if(j>=1&&grid[i][j-1]=='-'){
- String locationAdd=i+","+(j-1);
- int adjacentVertex=mapForVertices.get(locationAdd);
- Node node2=new Node(locationAdd,adjacentVertex);
- g.addEdge(node,node2);
- }
- if(j<=heightOfSurface-2&&grid[i][j+1]=='-'){
- String locationAdd=i+","+(j+1);
- int adjacentVertex=mapForVertices.get(locationAdd);
- Node node2=new Node(locationAdd,adjacentVertex);
- g.addEdge(node,node2);
- }
- if(j<=heightOfSurface-2-jump&&grid[1-i][j+jump]=='-'){
- String locationAdd=(1-i)+","+(j+jump);
- int adjacentVertex=mapForVertices.get(locationAdd);
- Node node2=new Node(locationAdd,adjacentVertex);
- g.addEdge(node,node2);
- }
- }
- }
- }
- int sourceNode=0;
- boolean[]visited=new boolean[numberOfVertices];
- Queue<Integer>nodes=new LinkedList<>();
- visited[sourceNode]=true;
- boolean solution=false;
- int[]distance=new int[numberOfVertices];
- for (int i = 0; i < distance.length; i++) {
- distance[i]=0;
- }
- nodes.add(sourceNode);
- while(!nodes.isEmpty()){
- int node=nodes.remove();
- if(goalNodes.contains(node)) {
- solution = true;
- break;
- }
- int count=0;
- for (Node adjacent : g.getAdjacentVertices(node)) {
- if (!visited[adjacent.index]) {
- count++;
- visited[adjacent.index] = true;
- String location = adjacent.info;
- distance[adjacent.index]+=1;
- String[] parts = location.split(",");
- int y = Integer.parseInt(parts[1]);
- if (y >= distance[adjacent.index]) {
- nodes.add(adjacent.index);
- }
- }
- }
- }
- if(solution)
- System.out.println("yes");
- else
- System.out.println("no");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement